Walktober

Problem

John participates in an annual walking competition called Walktober. The competition runs for a total of N days and tracks the daily steps of the participants for all the N days. Each participant will be assigned a unique ID ranging from 1 to M where M is the total number of registered participants. A global scoreboard is maintained tracking the daily steps of each participant.

John is determined to win Walktober this year and his goal is to score the maximum daily steps on each of the N days among all the participants. Having participated in Walktober last year as well, he wanted to know how many steps he fell short of in achieving his goal. Given the previous year scoreboard, calculate the minimum additional steps he needed over his last year score in order to achieve his goal of scoring the maximum daily steps every day.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains three integers M, N, and P denoting the total number of participants, the total number of days the competition runs, and the last year participant ID of John.
The next M lines describe the scoreboard of the previous year and contains N integers each. The j-th integer of the i-th line denotes the step count Si,j of the participant with ID i on the j-th day of the competition.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum total additional steps needed by John to achieve his goal.

My Solution

#include<bits/stdc++.h>

using namespace std;

int T;
int m,n,p;

int main() {
    cin>>T;
    for(int t=1;t<=T;t++) {
        cin>>m>>n>>p;
        vector<vector <int>> arr(m,vector<int>(n));
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                cin>>arr[i][j];
            }
        }
        int cnt=0;
        for(int j=0;j<n;j++) {
            int ma=arr[p-1][j];
            for(int i=0;i<m;i++) {
                if(arr[i][j]>ma)
                    ma=arr[i][j];
            }
            cnt+=ma-arr[p-1][j];
        }
        cout<<"Case #"<<t<<": "<<cnt<<endl;
    
    }
    
	return 0;
}

Curling

Problem

2022 is a year of the Winter Olympics! Curling has been one of the most popular winter sports as it requires skill, strategy, and sometimes a bit of luck.

In a curling game, two teams compete by sliding heavy granite stones on a long ice sheet. We call the teams the red team and the yellow team, as their stones are usually distinguished by the red and the yellow handle color. A curling game consists of several ends (subgames); in every end, the teams, each owning 8

stones, take turns to slide them across the long ice sheet toward a circular target area called the house. A stone may hit existing stones to change its own moving direction and other stones’ position (including knocking them out of play). Roughly speaking, the goal for a team is to make their stones as close to the center of the house as possible.

Geometrically, a house and a stone can be modeled as a circle and a disk (the region bounded by a circle), respectively, and the scoring rules at the conclusion of each end are formally summarized as follows.

• Each stone can be viewed as a disk of radius Rs on a 2-dimensional plane.
• The house is a circle of radius Rh centered at (0,0).
• Only stones in the house are considered in the scoring. A stone is in the house if any portion of the stone lies on or within the circle representing the house. Tangency also counts.
• A team is awarded 1 point for each of their own stones in the house such that no opponent’s stone is closer (in Euclidean distance) to the center than it. We assume in this problem that no two stones are equally close to the center (0,0).

Two teams are playing and have just delivered all their stones. The red team has N stones remaining on the curling sheet, centered at (X1,Y1),(X2,Y2),…,(XN,YN), while the yellow team has M stones remaining, centered at (Z1,W1),(Z2,W2),…,ZM,WM). Now you are asked to figure out the scores of both teams.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with a line containing the two space-separated integers Rs and Rh. The next line contains the integer N. Then N lines follow, the i-th line of which containing the two space-separated integers Xi and Yi.

After that, similarly, the next line contains the integer M. In the next M lines, the i-th line contains the two space-separated integers Zi and Wi.

Output

For each test case, output one line containing Case #x: y z, where x is the test case number (starting from 1), y is the score of the red team, and z is the score of the yellow team.

My Solution

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int T;
ll rs,rh,n,m;
ll x,y;
int main() {
    cin>>T;
    for(int t=1;t<=T;t++) {
        cin>>rs>>rh>>n;
        vector<ll> narr;
        for(int i=0;i<n;i++) {
            cin>>x>>y;
            if(x*x+y*y<=(rs+rh)*(rs+rh)) {
                narr.push_back(x*x+y*y);
            }
        }
        cin>>m;
        vector<ll> marr;
        for(int i=0;i<m;i++) {
            cin>>x>>y;
            if(x*x+y*y<=(rs+rh)*(rs+rh)) {
                marr.push_back(x*x+y*y);
            }
        }
        sort(narr.begin(), narr.end());
        sort(marr.begin(), marr.end());
        if(narr.size() && marr.size()) {
            if(narr[0]<marr[0]) {
                cout<<"Case #"<<t<<": "<<lower_bound(narr.begin(),narr.end(),marr[0])-narr.begin()<<" 0"<<endl;
            }
            else {
                cout<<"Case #"<<t<<": 0 "<<lower_bound(marr.begin(),marr.end(),narr[0])-marr.begin()<<endl;
            }
        }
        else{
            cout<<"Case #"<<t<<": "<<narr.size()<<" "<<marr.size()<<endl;
        }
    
    }
    
	return 0;
}

Happy Subarrays

Problem

Let us define F(B,L,R) as the sum of a subarray of an array B bounded by indices L and R (both inclusive). Formally, F(B,L,R)=BL*+*BL+1+⋯+B**R.

An array C of length K is called a happy array if all the prefix sums of C are non-negative. Formally, the terms F(C,1,1),F(C,1,2),…,F(C,1,K) are all non-negative. Given an array A of N integers, find the result of adding the sums of all the happy subarrays in the array A.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line consisting an integer N denoting the number of integers in the input array A. Then the next line contains N integers A1,A2,…,AN representing the integers in given input array A.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the result of adding the sums of all happy subarrays in the given input array A.

My Solution

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using vint = vector<int>;
#define all(x) (x).begin(), (x).end()

int T;
ll n;

int main() {
    cin>>T;
    for(int t=1;t<=T;t++) {
        cin>>n;
        vint a(n);
        for(int i=0;i<n;i++) {
            cin>>a[i];
        }
        vint presum(n+1);
        presum[0]=0;
        for(int i=0;i<n;i++) {
            presum[i+1]=presum[i]+a[i];
        }
        int res=0;
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                int sum = presum[j+1]-presum[i];
                if(sum>=0) {
                    res+=sum;
                    continue;
                }
                else {
                    break;
                }
            }
        }
        cout<<"Case #"<<t<<": "<<res<<endl;
    
    }
    
	return 0;
}

简陋版本，test set 2 TLE。

如何提升算法呢？

了解这个算法： All nearest smaller values algorithm

Cute Little Butterfly

Problem

In a forest of the magical world, there lies a garden full of magical creatures. The garden has plenty of flowers which are not just beautiful but also a source of energy for butterflies.

Consider the garden a 2D plane where the X-axis represents the ground, and the Y-axis represents the altitude. There are plants of infinite height on every non-negative integral point on the X-axis. There are N flowers in the garden, where the i-th flower is on the point (Xi, Yi) with the nectar of some energy value Ci.

Our cute little butterfly wants as much energy as possible to become strong. By going to the same position of a flower, the butterfly can consume its nectar and gain that flower’s energy value. Each flower’s nectar can only be consumed once.

The butterfly is initially at point (0,1018) with 0 units of energy and facing towards the right. At any point, the butterfly can:

• Move to a lower altitude, that is, from (x,y) to (x,y−1) only if its current altitude is positive (y>0).
• Move in the positive direction along the X-axis, that is, from (x,y) to (x+1,y) if it is facing right.
• Move in the negative direction along the X-axis, that is, from (x,y) to (x−1,y) if it is facing left.

• Change the direction it is facing (from left to right or vice versa). This will consume E units of energy.

  We know our butterfly is lazy, and it hates to move upwards during the journey. So, for this problem, we will assume that going upwards is not allowed. Also, energy can be negative at any point. Negative energy means the butterfly has spent more energy than it obtained from the flowers.

Find the maximum energy our cute butterfly can achieve.

Input

The first line of the input gives the number of test cases, T. **T** test cases follow. The first line of each test case contains two integers, **N** and **E**: the number of flowers and the energy required per turn, respectively. The next **N** lines describe the flowers. The *i-th line contains three integers, **Xi, Yi and Ci: the position and the energy value of the i-th flower, respectively.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum overall energy our cute butterfly can achieve.