Submission #284958

#	Time	Username	Problem	Language	Result	Execution time	Memory
284958		achibasadzishvili	Discharging (NOI20_discharging)	C++17	36 / 100	1105 ms	221900 KiB

Discharging

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,a[1000002];
ll dp[1000002],rm[1000002][21],po[2000002],pw[200],raod,mn;
ll lef[1000002],rig[1000002];
vector<ll>del[1000002];
ll get(ll x,ll y){
    ll lo = po[y - x + 1];
    if(rm[y][lo] > rm[x + pw[lo] - 1][lo])return rm[y][lo];
    return rm[x + pw[lo] - 1][lo];
}
ll ind(ll x,ll y){
    if(y == n)return -1;
    ll l = y + 1,r = n,mid,ind = -1;
    while(r >= l){
        mid = (l + r) / 2;
        if(dp[x] + get(x + 1 , mid) * (n - x) >= dp[y] + get(y + 1 , mid) * (n - y)){
            r = mid - 1;
            ind = mid;
        }
        else
            l = mid + 1;
    }
    return ind;
}
void delet(ll x){
    if(lef[x] == rig[x] && lef[x] == -1)return;
    if(lef[x] == -1){
        lef[rig[x]] = -1;
        mn = rig[x];
        rig[x] = -1;
        return;
    }
    rig[lef[x]] = rig[x];
    lef[rig[x]] = lef[x];
    ll cur = ind(lef[x] , rig[x]);
    if(cur == -1){
        lef[x] = rig[x] = -1;
        return;
    }
    del[cur].pb(lef[x]);
    lef[x] = rig[x] = -1;
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    int cl = clock();
    //n = 1000000;
    //for(int i=1; i<=n; i++)
    //    a[i] = n-i+1;
    pw[0] = 1;
    
    for(int i=1; i<=21; i++){
        pw[i] = pw[i - 1] * 2;
        for(int j=pw[i - 1]; j<pw[i]; j++){
            if(j <= 1000000)
                po[j] = i - 1;
        }
    }
    for(int i=0; i<=n; i++)
        lef[i] = rig[i] = -1;
    for(int i=1; i<=n; i++){
        rm[i][0] = a[i];
        for(int j=1; j<=20; j++){
            if(i - pw[j] + 1 >= 1)
                rm[i][j] = max(rm[i][j - 1] , rm[i - pw[j - 1]][j - 1]);
        }
    }
    //cout << clock() - cl << '\n';
    for(int i=1; i<=n; i++){
        for(int j=0; j<del[i].size(); j++){
            delet(del[i][j]);
        }
        ll in = 0,mx=0;
        dp[i] = 100000000000000;
        for(int j=i; j>=1; j--){
            mx = max(mx , a[j]);
            if(dp[j - 1] + mx * (n - j + 1) < dp[i]){
                in = j - 1;
                dp[i] = min(dp[i] , dp[j - 1] + mx * (n - j + 1));
            }
        }
        dp[i] = dp[mn] + get(mn + 1 , i) * (n - mn);
        rig[i - 1] = i;
        lef[i] = i - 1;
        ll cur = ind(i - 1 , i);
        if(cur != -1)
            del[cur].pb(i - 1);
    }
    //cout << "time: " << clock() - cl << " " << raod << '\n';
    cout << dp[n];
    
    
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:49:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   49 |     scanf("%d",&n);
      |            ~^  ~~
      |             |  |
      |             |  long long int*
      |             int*
      |            %lld
Discharging.cpp:51:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   51 |         scanf("%d",&a[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
Discharging.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
Discharging.cpp:80:12: warning: variable 'in' set but not used [-Wunused-but-set-variable]
   80 |         ll in = 0,mx=0;
      |            ^~
Discharging.cpp:53:9: warning: unused variable 'cl' [-Wunused-variable]
   53 |     int cl = clock();
      |         ^~
Discharging.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Discharging.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 14 / 14
• Subtask 6: 0 / 28