# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
919690 | 2024-02-01T12:52:36 Z | Aiperiii | Split the sequence (APIO14_sequence) | C++14 | 77 ms | 9248 KB |
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; bool ok[500000]; signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n,k; cin>>n>>k; vector <int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector <vector <int> > v; vector <int> ids; for(int i=0;i<n;i++){ ids.pb(i); } v.pb(ids); vector <int> res; int ans=0; while(k--){ int mx=-10,div=0,ind=0; for(int j=0;j<v.size();j++){ if(ok[j])continue; vector <int> pr; int sum=0; for(int i=0;i<v[j].size();i++){ sum+=a[v[j][i]]; pr.pb(sum); } for(int i=0;i<pr.size();i++){ int x=pr.back()-pr[i]; if(mx<x*pr[i]){ mx=x*pr[i]; div=i; ind=j; } } } ok[ind]=1; vector <int> g1,g2; res.pb(v[ind][div]); for(int i=0;i<v[ind].size();i++){ if(i<=div)g1.pb(v[ind][i]); else g2.pb(v[ind][i]); } v.pb(g1);v.pb(g2); ans+=mx; } cout<<ans<<"\n"; for(auto x :res)cout<<x+1<<" "; cout<<"\n"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | contestant found the optimal answer: 108 == 108 |
2 | Incorrect | 0 ms | 344 KB | contestant didn't find the optimal answer: 951 < 999 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | contestant didn't find the optimal answer: 1093726 < 1093956 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 440 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 1 ms | 344 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Correct | 1 ms | 344 KB | contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 | Correct | 1 ms | 348 KB | contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 | Incorrect | 1 ms | 348 KB | contestant didn't find the optimal answer: 1019625813 < 1019625819 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | contestant didn't find the optimal answer: 21419072 < 21503404 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 948 KB | contestant didn't find the optimal answer: 1794250000 < 1818678304 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 4928 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 15 ms | 5184 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Incorrect | 77 ms | 9248 KB | contestant didn't find the optimal answer: 497009314607795353 < 497313449256899208 |
4 | Halted | 0 ms | 0 KB | - |