CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Results
Submission details
Task:Good grades
Sender:aalto2024j_003
Submission time:2024-11-06 17:06:40 +0200
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.01 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.01 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.01 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.01 sdetails
#49ACCEPTED0.00 sdetails
#50ACCEPTED0.07 sdetails
#51ACCEPTED0.05 sdetails
#52ACCEPTED0.05 sdetails
#53ACCEPTED0.07 sdetails
#54ACCEPTED0.11 sdetails
#55ACCEPTED0.04 sdetails
#56ACCEPTED0.10 sdetails
#57ACCEPTED0.01 sdetails
#58ACCEPTED0.10 sdetails
#59ACCEPTED0.01 sdetails

Compiler report

input/code.cpp: In function 'void solve()':
input/code.cpp:60:20: warning: statement has no effect [-Wunused-value]
   60 | #define debug(...) 42
      |                    ^~
input/code.cpp:92:13: note: in expansion of macro 'debug'
   92 |             debug(g, i, dp[g][i]);
      |             ^~~~~
input/code.cpp:60:20: warning: statement has no effect [-Wunused-value]
   60 | #define debug(...) 42
      |                    ^~
input/code.cpp:96:5: note: in expansion of macro 'debug'
   96 |     debug(dp[k][n]);
      |     ^~~~~
input/code.cpp:60:20: warning: statement has no effect [-Wunused-value]
   60 | #define debug(...) 42
      |                    ^~
input/code.cpp:105:5: note: in expansion of macro 'debug'
  105 |     debug(path);
      |     ^~~~~

Code

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 505;
const int INF = 1e18 + 7;

int n, k;
pair<int, int> a[N];
int dp[N][N];
int par[N][N];
int ans[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);

    for (int g = 0; g <= k; g++) for (int i = 0; i <= n; i++) dp[g][i] = -INF;

    dp[0][0] = 0;
    for (int g = 1; g <= k; g++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                int lst = dp[g - 1][j] + a[j + 1].first * (i - j);
                if (lst > dp[g][i]) {
                    dp[g][i] = lst;
                    par[g][i] = j;
                }
            }
            debug(g, i, dp[g][i]);
        }
    }

    debug(dp[k][n]);
    vi path;
    int curg = k, curi = n;
    while (curg) {
        path.push_back(curi);
        curi = par[curg][curi];
        curg--;
    }
    path.push_back(0);
    debug(path);
    reverse(all(path));
    for (int i = 0, g = 1; i + 1 < sz(path); i++, g++) {
        for (int x = path[i] + 1; x <= path[i + 1]; x++) {
            ans[a[x].second] = g;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // RTE if input wrong datatype

    solve();
}

Test details

Test 1

Verdict: ACCEPTED

input
1 1

correct output

user output

Test 2

Verdict: ACCEPTED

input
2 2
7 6 

correct output
2 1 

user output
2 1 

Test 3

Verdict: ACCEPTED

input
2 1
7 7 

correct output
1 1 

user output
1 1 

Test 4

Verdict: ACCEPTED

input
2 2
7 1 

correct output
2 1 

user output
2 1 

Test 5

Verdict: ACCEPTED

input
3 1
5 10 8 

correct output
1 1 1 

user output
1 1 1 

Test 6

Verdict: ACCEPTED

input
3 1
6 10 2 

correct output
1 1 1 

user output
1 1 1 

Test 7

Verdict: ACCEPTED

input
4 1
10 10 4 2 

correct output
1 1 1 1 

user output
1 1 1 1 

Test 8

Verdict: ACCEPTED

input
4 4
5 1 5 4 

correct output
3 1 4 2 

user output
3 1 4 2 

Test 9

Verdict: ACCEPTED

input
4 2
1 6 7 1 

correct output
1 2 2 1 

user output
1 2 2 1 

Test 10

Verdict: ACCEPTED

input
5 3
6 8 9 7 9 

correct output
1 2 3 1 3 

user output
1 2 3 2 3 

Test 11

Verdict: ACCEPTED

input
5 3
10 8 10 1 2 

correct output
3 2 3 1 1 

user output
3 2 3 1 1 

Test 12

Verdict: ACCEPTED

input
5 3
2 1 10 6 10 

correct output
1 1 3 2 3 

user output
1 1 3 2 3 

Test 13

Verdict: ACCEPTED

input
5 3
1 8 9 3 2 

correct output
1 3 3 2 1 

user output
1 3 3 2 2 

Test 14

Verdict: ACCEPTED

input
5 5
10 6 2 10 9 

correct output
4 2 1 5 3 

user output
4 2 1 5 3 

Test 15

Verdict: ACCEPTED

input
5 2
1 9 9 3 4 

correct output
1 2 2 1 1 

user output
1 2 2 1 1 

Test 16

Verdict: ACCEPTED

input
5 5
10 4 3 9 1 

correct output
5 3 2 4 1 

user output
5 3 2 4 1 

Test 17

Verdict: ACCEPTED

input
5 1
3 8 4 5 10 

correct output
1 1 1 1 1 

user output
1 1 1 1 1 

Test 18

Verdict: ACCEPTED

input
5 5
1 10 3 9 4 

correct output
1 5 2 4 3 

user output
1 5 2 4 3 

Test 19

Verdict: ACCEPTED

input
5 1
4 6 5 5 1 

correct output
1 1 1 1 1 

user output
1 1 1 1 1 

Test 20

Verdict: ACCEPTED

input
10 6
6 8 9 7 9 6 9 5 7 7 

correct output
2 4 5 3 5 2 6 1 3 3 

user output
2 5 6 4 6 3 6 1 4 4 

Test 21

Verdict: ACCEPTED

input
10 5
10 8 10 1 2 4 10 2 3 1 

correct output
5 4 5 1 2 3 5 2 2 1 

user output
5 4 5 1 2 3 5 2 3 1 

Test 22

Verdict: ACCEPTED

input
10 5
2 1 10 6 10 5 5 5 4 4 

correct output
1 1 5 4 5 3 3 3 2 2 

user output
2 1 5 4 5 4 4 4 3 3 

Test 23

Verdict: ACCEPTED

input
10 6
1 8 9 3 2 6 6 9 5 9 

correct output
1 5 6 2 1 4 4 6 3 6 

user output
1 5 6 2 2 4 4 6 3 6 

Test 24

Verdict: ACCEPTED

input
10 10
10 6 2 10 9 8 7 7 6 3 

correct output
9 3 1 10 8 7 5 6 4 2 

user output
9 3 1 10 8 7 5 6 4 2 

Test 25

Verdict: ACCEPTED

input
10 3
1 9 9 3 4 10 10 5 1 7 

correct output
1 3 3 1 2 3 3 2 1 2 

user output
1 3 3 1 2 3 3 2 1 2 

Test 26

Verdict: ACCEPTED

input
10 9
10 4 3 9 1 1 4 2 10 6 

correct output
8 4 3 7 1 1 5 2 9 6 

user output
9 5 4 8 1 2 6 3 9 7 

Test 27

Verdict: ACCEPTED

input
10 1
3 8 4 5 10 8 5 10 4 6 

correct output
1 1 1 1 1 1 1 1 1 1 

user output
1 1 1 1 1 1 1 1 1 1 

Test 28

Verdict: ACCEPTED

input
10 9
1 10 3 9 4 6 9 3 5 1 

correct output
1 9 2 7 4 6 8 3 5 1 

user output
1 9 3 8 5 7 8 4 6 2 

Test 29

Verdict: ACCEPTED

input
10 1
4 6 5 5 1 2 4 2 1 3 

correct output
1 1 1 1 1 1 1 1 1 1 

user output
1 1 1 1 1 1 1 1 1 1 

Test 30

Verdict: ACCEPTED

input
100 55
636562060 767928734 906523441 ...

correct output
32 42 50 33 51 29 50 23 35 37 ...

user output
32 42 50 33 51 29 50 23 35 37 ...

Test 31

Verdict: ACCEPTED

input
100 42
773442532 122816 137572579 324...

correct output
34 1 8 16 9 13 6 20 10 19 18 3...

user output
34 1 8 16 9 13 6 20 10 19 18 3...

Test 32

Verdict: ACCEPTED

input
100 44
198730372 27838076 590195590 4...

correct output
9 1 28 21 23 20 15 16 7 10 36 ...

user output
9 1 28 21 23 20 15 16 7 10 36 ...

Test 33

Verdict: ACCEPTED

input
100 56
75940263 760367935 901888417 3...

correct output
6 44 51 19 8 33 36 54 29 54 1 ...

user output
6 44 51 19 8 33 36 54 29 54 1 ...

Test 34

Verdict: ACCEPTED

input
100 97
967034924 587586158 185430194 ...

correct output
94 59 19 88 79 67 77 64 27 15 ...

user output
94 59 19 88 79 67 77 64 27 15 ...

Test 35

Verdict: ACCEPTED

input
100 23
59249204 934941692 892631472 2...

correct output
2 22 21 6 10 23 12 3 15 11 19 ...

user output
2 22 21 6 10 23 12 3 15 11 19 ...

Test 36

Verdict: ACCEPTED

input
100 90
356460601 224848374 881788059 ...

correct output
23 14 83 4 1 28 8 54 7 48 56 3...

user output
23 14 83 4 1 28 8 54 7 48 56 3...

Test 37

Verdict: ACCEPTED

input
100 8
244103474 837431431 342493822 ...

correct output
2 7 3 5 7 5 3 6 3 5 1 1 5 3 1 ...

user output
2 7 3 5 7 5 3 6 3 5 1 1 5 3 1 ...

Test 38

Verdict: ACCEPTED

input
100 88
11934038 257096283 933290530 4...

correct output
1 24 83 40 56 80 23 44 1 62 46...

user output
1 24 83 40 56 80 23 44 1 62 46...

Test 39

Verdict: ACCEPTED

input
100 2
391337048 538883744 535937150 ...

correct output
1 2 2 2 1 1 1 1 1 1 2 1 1 1 1 ...

user output
1 2 2 2 1 1 1 1 1 1 2 1 1 1 1 ...

Test 40

Verdict: ACCEPTED

input
200 110
636562060 767928734 906523441 ...

correct output
69 86 99 70 101 61 100 47 74 7...

user output
69 86 99 70 101 61 100 47 74 7...

Test 41

Verdict: ACCEPTED

input
200 84
773442532 122816 137572579 324...

correct output
66 1 14 28 16 23 11 36 18 35 3...

user output
66 1 14 28 16 23 11 36 18 35 3...

Test 42

Verdict: ACCEPTED

input
200 88
198730372 27838076 590195590 4...

correct output
17 3 53 42 45 40 29 30 13 18 6...

user output
17 3 53 42 45 40 29 30 13 18 6...

Test 43

Verdict: ACCEPTED

input
200 111
75940263 760367935 901888417 3...

correct output
8 85 100 35 14 62 71 106 51 10...

user output
8 85 100 35 14 62 71 106 51 10...

Test 44

Verdict: ACCEPTED

input
200 194
967034924 587586158 185430194 ...

correct output
185 114 39 173 151 128 147 124...

user output
185 114 39 173 151 128 147 124...

Test 45

Verdict: ACCEPTED

input
200 45
59249204 934941692 892631472 2...

correct output
3 43 41 11 19 45 25 5 30 21 37...

user output
3 43 41 11 19 45 25 5 30 21 37...

Test 46

Verdict: ACCEPTED

input
200 179
356460601 224848374 881788059 ...

correct output
54 33 162 8 4 61 15 113 14 99 ...

user output
54 33 162 8 4 61 15 113 14 99 ...

Test 47

Verdict: ACCEPTED

input
200 16
244103474 837431431 342493822 ...

correct output
4 14 6 8 13 9 6 10 5 10 2 2 8 ...

user output
4 14 6 8 13 9 6 10 5 10 2 2 8 ...

Test 48

Verdict: ACCEPTED

input
200 175
11934038 257096283 933290530 4...

correct output
2 40 165 67 105 157 37 77 2 11...

user output
2 40 165 67 105 157 37 77 2 11...

Test 49

Verdict: ACCEPTED

input
200 3
391337048 538883744 535937150 ...

correct output
2 2 2 2 1 1 1 1 1 1 3 2 1 1 1 ...

user output
2 2 2 2 1 1 1 1 1 1 3 2 1 1 1 ...

Test 50

Verdict: ACCEPTED

input
500 275
636562060 767928734 906523441 ...

correct output
176 215 251 178 254 161 252 12...

user output
176 215 251 178 254 161 252 12...

Test 51

Verdict: ACCEPTED

input
500 209
773442532 122816 137572579 324...

correct output
163 1 31 72 37 57 23 89 45 87 ...

user output
163 1 31 72 37 57 23 89 45 87 ...

Test 52

Verdict: ACCEPTED

input
500 218
198730372 27838076 590195590 4...

correct output
42 8 130 102 113 97 73 75 34 4...

user output
42 8 130 102 113 97 73 75 34 4...

Test 53

Verdict: ACCEPTED

input
500 276
75940263 760367935 901888417 3...

correct output
20 205 249 85 32 149 165 267 1...

user output
20 205 249 85 32 149 165 267 1...

Test 54

Verdict: ACCEPTED

input
500 484
967034924 587586158 185430194 ...

correct output
469 290 97 438 372 322 367 317...

user output
469 290 97 438 372 322 367 317...

Test 55

Verdict: ACCEPTED

input
500 111
59249204 934941692 892631472 2...

correct output
5 104 100 24 42 109 55 9 70 46...

user output
5 104 100 24 42 109 55 9 70 46...

Test 56

Verdict: ACCEPTED

input
500 447
356460601 224848374 881788059 ...

correct output
154 88 394 30 18 168 46 279 43...

user output
154 88 394 30 18 168 46 279 43...

Test 57

Verdict: ACCEPTED

input
500 39
244103474 837431431 342493822 ...

correct output
9 33 13 18 31 19 13 23 11 21 3...

user output
9 33 13 18 31 19 13 23 11 21 3...

Test 58

Verdict: ACCEPTED

input
500 437
11934038 257096283 933290530 4...

correct output
7 101 407 167 251 388 97 191 7...

user output
7 101 407 167 251 388 97 191 7...

Test 59

Verdict: ACCEPTED

input
500 6
391337048 538883744 535937150 ...

correct output
3 4 4 4 1 2 3 2 1 2 6 3 2 2 2 ...

user output
3 4 4 4 1 2 3 2 1 2 6 3 2 2 2 ...