oj.uz

Submission #881785

# Submission time Handle Problem Language Result Execution time Memory
881785 2023-12-01T22:38:33 Z andro Stove (JOI18_stove) C++14
50 / 100
 1000 ms 8016 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    int A[n+1];
    for(int i=0;i<=n;i++)A[i]=0;
    A[n]=1;
    int ans=0;
    ans+=a[n]+1-a[1];
    k--;
    while(k--){
        vector<pair<int,int>>v;
        int suf[n+1];
        suf[n]=n;
        for(int i=n-1;i>=1;i--){
            if(A[i])suf[i]=i;
            else suf[i]=suf[i+1];
        }
        int pret=1;
        for(int i=1;i<=n;i++){
            if(A[i]){
                pret=i;
                continue;
            }
            int R=ans;
            int sl=suf[i];
            //R+=-(a[sl]+1-a[pret+1])+a[sl]+1-a[i+1]+a[i]+1-a[pret+1];
            R+=-a[i+1]+a[i]+1;
            //R-=a[sl]+1-a[pret+1];
            //R+=a[sl]+1-a[i+1];
            //R+=a[i]+1-a[pret+1];
            v.push_back({R,i});
        }
        sort(v.begin(),v.end());
        int b=v[0].second;
        A[b]=1;
        int sl=-1;
        for(int i=b+1;i<=n;i++){
            if(A[i]){
                sl=i;
                break;
            }
        }
        pret=1;
        for(int i=1;i<b;i++){
            if(A[i]){
                pret=i;
            }
        }
        //ans-=a[sl]+1-a[pret+1];
        //ans+=a[sl]+1-a[b+1];
        //ans+=a[b]+1-a[pret+1];
        //ans+=-(a[sl]+1-a[pret+1])+a[sl]+1-a[b+1]+a[b]+1-a[pret+1];
        ans+=-a[b+1]+a[b]+1;
    }
    cout<<ans;
}
/*
a[i]+1-a[pret];
pret=i+1;

*/

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:32:17: warning: unused variable 'sl' [-Wunused-variable]
   32 |             int sl=suf[i];
      |                 ^~
stove.cpp:25:13: warning: variable 'pret' set but not used [-Wunused-but-set-variable]
   25 |         int pret=1;
      |             ^~~~
stove.cpp:43:13: warning: variable 'sl' set but not used [-Wunused-but-set-variable]
   43 |         int sl=-1;
      |             ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 18 ms 672 KB Output is correct
12 Correct 145 ms 648 KB Output is correct
13 Correct 235 ms 604 KB Output is correct
14 Correct 264 ms 648 KB Output is correct
15 Correct 260 ms 648 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 18 ms 672 KB Output is correct
12 Correct 145 ms 648 KB Output is correct
13 Correct 235 ms 604 KB Output is correct
14 Correct 264 ms 648 KB Output is correct
15 Correct 260 ms 648 KB Output is correct
16 Correct 96 ms 7376 KB Output is correct
17 Correct 987 ms 7440 KB Output is correct
18 Execution timed out 1060 ms 8016 KB Time limit exceeded
19 Halted 0 ms 0 KB -