# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
84906 | 2018-11-17T18:35:30 Z | ToadDaveski | Gift (IZhO18_nicegift) | C++14 | 2000 ms | 104264 KB |
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second using namespace std; vector <vector <pair <ll,ll> > > q; ll a[2000001]; map <ll,ll> poz; vector <ll> ans; int main() { ll n,k,i,j,ma=0; cin>>n>>k; ll sum=0,part; for(i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; ma=max(ma,a[i]); } part=sum/k; if (sum%k || part<ma ) { cout<<-1; return 0; } sum=0; vector <pair <ll,ll> > temp; for(i=1;i<=n;i++) { sum+=a[i]; if (sum>=part) { temp.push_back({a[i]-(sum-part),i}); q.push_back(temp); temp.clear(); sum=sum-part; if (sum) temp.push_back({sum,i}); } else { temp.push_back({a[i],i}); } } while(true) { ll mi=1e18; for(i=0;i<k;i++) mi=min(mi,q[i][poz[i]].fr); ans.push_back(mi); ll kol=0; for(i=0;i<k;i++) { ans.push_back(q[i][poz[i]].sc); q[i][poz[i]].fr-=mi; if (poz[i]<q[i].size() && !q[i][poz[i]].fr) { poz[i]++; if (poz[i]<q[i].size()) kol++; } } if (!kol) break; } ll toad=0; cout<<ans.size()/(k+1)<<endl; while(toad<ans.size()) { cout<<ans[toad]<<" "; if (((toad+1)%(k+1))==0) cout<<endl; toad++; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | n=4 |
2 | Correct | 2 ms | 484 KB | n=3 |
3 | Correct | 2 ms | 484 KB | n=3 |
4 | Correct | 2 ms | 484 KB | n=4 |
5 | Correct | 2 ms | 484 KB | n=4 |
6 | Correct | 2 ms | 484 KB | n=2 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | n=4 |
2 | Correct | 2 ms | 484 KB | n=3 |
3 | Correct | 2 ms | 484 KB | n=3 |
4 | Correct | 2 ms | 484 KB | n=4 |
5 | Correct | 2 ms | 484 KB | n=4 |
6 | Correct | 2 ms | 484 KB | n=2 |
7 | Correct | 2 ms | 484 KB | n=5 |
8 | Correct | 2 ms | 484 KB | n=8 |
9 | Correct | 2 ms | 484 KB | n=14 |
10 | Correct | 2 ms | 484 KB | n=11 |
11 | Correct | 96 ms | 3852 KB | n=50000 |
12 | Correct | 91 ms | 3852 KB | n=50000 |
13 | Correct | 2 ms | 3852 KB | n=10 |
14 | Correct | 4 ms | 3852 KB | n=685 |
15 | Correct | 3 ms | 3852 KB | n=623 |
16 | Correct | 4 ms | 3852 KB | n=973 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | n=4 |
2 | Correct | 2 ms | 484 KB | n=3 |
3 | Correct | 2 ms | 484 KB | n=3 |
4 | Correct | 2 ms | 484 KB | n=4 |
5 | Correct | 2 ms | 484 KB | n=4 |
6 | Correct | 2 ms | 484 KB | n=2 |
7 | Correct | 2 ms | 484 KB | n=5 |
8 | Correct | 2 ms | 484 KB | n=8 |
9 | Correct | 2 ms | 484 KB | n=14 |
10 | Correct | 2 ms | 484 KB | n=11 |
11 | Correct | 96 ms | 3852 KB | n=50000 |
12 | Correct | 91 ms | 3852 KB | n=50000 |
13 | Correct | 2 ms | 3852 KB | n=10 |
14 | Correct | 4 ms | 3852 KB | n=685 |
15 | Correct | 3 ms | 3852 KB | n=623 |
16 | Correct | 4 ms | 3852 KB | n=973 |
17 | Correct | 4 ms | 3852 KB | n=989 |
18 | Correct | 4 ms | 3852 KB | n=563 |
19 | Correct | 7 ms | 3852 KB | n=592 |
20 | Correct | 6 ms | 3852 KB | n=938 |
21 | Correct | 5 ms | 3852 KB | n=747 |
22 | Correct | 5 ms | 3852 KB | n=991 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1735 ms | 58020 KB | n=1000000 |
2 | Correct | 943 ms | 58020 KB | n=666666 |
3 | Correct | 467 ms | 58020 KB | n=400000 |
4 | Correct | 1042 ms | 61584 KB | n=285714 |
5 | Correct | 25 ms | 61584 KB | n=20000 |
6 | Correct | 770 ms | 61584 KB | n=181818 |
7 | Correct | 17 ms | 61584 KB | n=10000 |
8 | Correct | 136 ms | 61584 KB | n=6666 |
9 | Correct | 7 ms | 61584 KB | n=4000 |
10 | Correct | 905 ms | 61584 KB | n=2857 |
11 | Correct | 7 ms | 61584 KB | n=2000 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | n=4 |
2 | Correct | 2 ms | 484 KB | n=3 |
3 | Correct | 2 ms | 484 KB | n=3 |
4 | Correct | 2 ms | 484 KB | n=4 |
5 | Correct | 2 ms | 484 KB | n=4 |
6 | Correct | 2 ms | 484 KB | n=2 |
7 | Correct | 2 ms | 484 KB | n=5 |
8 | Correct | 2 ms | 484 KB | n=8 |
9 | Correct | 2 ms | 484 KB | n=14 |
10 | Correct | 2 ms | 484 KB | n=11 |
11 | Correct | 96 ms | 3852 KB | n=50000 |
12 | Correct | 91 ms | 3852 KB | n=50000 |
13 | Correct | 2 ms | 3852 KB | n=10 |
14 | Correct | 4 ms | 3852 KB | n=685 |
15 | Correct | 3 ms | 3852 KB | n=623 |
16 | Correct | 4 ms | 3852 KB | n=973 |
17 | Correct | 4 ms | 3852 KB | n=989 |
18 | Correct | 4 ms | 3852 KB | n=563 |
19 | Correct | 7 ms | 3852 KB | n=592 |
20 | Correct | 6 ms | 3852 KB | n=938 |
21 | Correct | 5 ms | 3852 KB | n=747 |
22 | Correct | 5 ms | 3852 KB | n=991 |
23 | Correct | 1735 ms | 58020 KB | n=1000000 |
24 | Correct | 943 ms | 58020 KB | n=666666 |
25 | Correct | 467 ms | 58020 KB | n=400000 |
26 | Correct | 1042 ms | 61584 KB | n=285714 |
27 | Correct | 25 ms | 61584 KB | n=20000 |
28 | Correct | 770 ms | 61584 KB | n=181818 |
29 | Correct | 17 ms | 61584 KB | n=10000 |
30 | Correct | 136 ms | 61584 KB | n=6666 |
31 | Correct | 7 ms | 61584 KB | n=4000 |
32 | Correct | 905 ms | 61584 KB | n=2857 |
33 | Correct | 7 ms | 61584 KB | n=2000 |
34 | Correct | 61 ms | 61584 KB | n=23514 |
35 | Correct | 57 ms | 61584 KB | n=23514 |
36 | Correct | 4 ms | 61584 KB | n=940 |
37 | Correct | 2 ms | 61584 KB | n=2 |
38 | Correct | 297 ms | 61584 KB | n=100000 |
39 | Correct | 291 ms | 61584 KB | n=100000 |
40 | Correct | 3 ms | 61584 KB | n=10 |
41 | Correct | 3 ms | 61584 KB | n=100 |
42 | Correct | 13 ms | 61584 KB | n=1000 |
43 | Execution timed out | 2056 ms | 104264 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |