Codeforces Round ＃645 (Div. 2)

Codeforces Round #645 (Div. 2)

Notes ：

Official explanation ：https://codeforces.com/blog/entry/77869

C Problem thinking

D Problem thinking , The use of inference can be skillfully solved by circulation （ You can also use binary trees ）

C. Celex Update

Category ： thinking

Observation reveals ,

1. Go all the way down , And then to the right , And will be the largest .

2. Change the right step to the down step each time , The sum can be added 1.

   Above description sum The value of is increasing , And the incremental value is 1.

So if you know sum Maximum and minimum of , You can know how many sum.

So if you know that there is n That's ok m Column ,

Then the difference is
$$（0+n-1)\ast n+(n-1)\ast (m-n-1)=n\ast m-n-m+1$$

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
    int cas;
    scanf("%d",&cas);
    ll x1,y1,x2,y2;
    while(cas--)
    {
        cin>>x1>>y1>>x2>>y2;
        ll n=x2-x1+1;
        ll m=y2-y1+1;
        ll ans=n*m-n-m+1+1;
        cout<<ans<<endl;
    }
    return 0;
}C+=

D. The Best Vacation

Category ： thinking , Use inference to solve （ You can also use binary trees ）

subject ： Yes n Months , Everyone with a a_i God , The daily value is i, Select consecutive x God , bring sum Maximum .

Answer key ：

1. Use inference ： The last day of every consecutive day must be the last day of that month ,

prove ： If not , Suppose this last day is $a_{ix}$, So moving forward is $a_{i(x+1)}$, that sum It can only be less than or equal to the previous one sum, So the biggest sum Only on the last day .

2. Because it can not be in the same year , That is, the array can loop , So double the length of the array .

#include <iostream>
#include <algorithm>
#include <vector>

#define int long long

using namespace std;

signed main() {
    freopen("in.text","r",stdin);
    int n, len;
    cin >> n >> len;
    vector<int> A(2 * n);  // It is used to record the days of each month 
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        A[n + i] = A[i];
    }
    n *= 2;

    vector<int> B = {0}, C = {0}; //B It is used to record the cumulative sum of days ,C Used to record the cumulative sum of values 
    for (int i = 0; i < n; i++)
        B.push_back(B.back() + A[i]);
    for (int i = 0; i < n; i++) {
        C.push_back(C.back() + (A[i] * (A[i] + 1)) / 2);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (B[i + 1] >= len) {
            int z = upper_bound(B.begin(), B.end(), B[i + 1] - len) - B.begin();
            int cnt = C[i + 1] - C[z];
            int days = B[i + 1] - B[z];
            int too = len - days;
            cnt += ((A[z - 1] * (A[z - 1] + 1)) / 2);
            cnt -= (((A[z - 1] - too) * (A[z - 1] - too + 1)) / 2);
            ans = max(ans, cnt);
        }
    }
    cout << ans;
}