CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Results
Submission details
Task:Good grades
Sender:aalto2024j_006
Submission time:2024-11-06 17:47:16 +0200
Language:C++ (C++17)
Status:READY
Result:
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.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.01 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
#250.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#34ACCEPTED0.01 sdetails
#350.00 sdetails
#36ACCEPTED0.01 sdetails
#370.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#400.01 sdetails
#410.01 sdetails
#420.01 sdetails
#430.01 sdetails
#44ACCEPTED0.01 sdetails
#450.01 sdetails
#460.01 sdetails
#470.00 sdetails
#48ACCEPTED0.01 sdetails
#490.00 sdetails
#500.07 sdetails
#510.05 sdetails
#520.06 sdetails
#530.07 sdetails
#54ACCEPTED0.11 sdetails
#550.03 sdetails
#56ACCEPTED0.10 sdetails
#570.01 sdetails
#58ACCEPTED0.10 sdetails
#590.01 sdetails

Compiler report

input/code.cpp: In function 'void solve()':
input/code.cpp:26:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < nums.size(); i++)
      |                     ~~^~~~~~~~~~~~~
input/code.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int j = 1; j < dp[0].size(); j++)
      |                     ~~^~~~~~~~~~~~~~
input/code.cpp:47:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 1; i < dp.size(); i++)
      |                         ~~^~~~~~...

Code

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <cmath>
#include <functional>
#include <type_traits>
#include <fstream>
#include <bitset>
 
#define int long long
using namespace std;
 

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<pair<int, int>> nums(n);
    for (int i = 0; i < nums.size(); i++)
    {
        int a;
        cin >> a;
        nums[i] = {a, i};
    }

    sort(nums.begin(), nums.end());

    /*
    for (int i = 0; i < nums.size(); i++)
        cout << nums[i].first << " ";
    cout << endl;
    */

    vector<vector<pair<int, int>>> dp(nums.size()+1, vector<pair<int, int>>(k+1, {LLONG_MIN / 2, 0}));
    vector<vector<int>> dpMem(nums.size()+1, vector<int>(k+1, 0));
    dp[0][0] = {0, 0};

    for (int j = 1; j < dp[0].size(); j++)
    {
        for (int i = 1; i < dp.size(); i++)
        {
            // p1: create new, p2: continue other
            int maxIdx = 0;
            int maxVal = LLONG_MIN / 2;
            for (int t = 0; t < i; t++)
            {
                int cand = dp[t][j-1].first + (i-t) * nums[t].first;
                if (cand > maxVal)
                {
                    maxVal = cand;
                    maxIdx = t;
                }
            }
            dp[i][j] = {maxVal, 0};
            dpMem[maxIdx+1][j] = 1;
            /*
            int p1 = dp[i-1][j-1].first + nums[i-1].first;
            int p2 = dp[i-1][j].first + dp[i-1][j].second;
            if (p1 >= p2)
            {
                dp[i][j] = {p1, nums[i-1].first};
                dpMem[i][j] = 1;
            }
            else
            {
                dp[i][j] = {p2, dp[i-1][j].second};
            }
            */
            //cout << dp[i][j].first << "-" << dp[i][j].second << "-" << dpMem[i][j] << "       ";
        }
        //cout << endl;
    }

    vector<int> res(n);

    int j = k;
    for (int i = dp.size()-1; i > 0; i--)
    {
        res[nums[i-1].second] = j;
        if (dpMem[i][j] == 1)
            j--;
    }

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";

}
 
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t = 1;
 
    //cin >> t;
    //ifstream f("testcase.txt");
    //cin.rdbuf(f.rdbuf());
 
    for (int i = 0; i < t; i++)
        solve();
 
    return 0;
}

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 1 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 1 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:

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 1 3 3 1 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:

input
100 55
636562060 767928734 906523441 ...

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

user output
31 42 50 32 51 28 50 22 35 37 ...

Test 31

Verdict:

input
100 42
773442532 122816 137572579 324...

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

user output
33 1 5 14 6 10 3 17 8 17 16 30...

Test 32

Verdict:

input
100 44
198730372 27838076 590195590 4...

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

user output
6 1 26 19 21 18 11 12 3 7 35 3...

Test 33

Verdict:

input
100 56
75940263 760367935 901888417 3...

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

user output
5 44 51 18 7 32 36 54 28 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:

input
100 23
59249204 934941692 892631472 2...

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

user output
1 22 21 2 7 23 9 1 14 8 19 7 1...

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:

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
1 7 1 2 4 2 1 2 1 2 1 1 2 1 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:

input
200 110
636562060 767928734 906523441 ...

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

user output
67 85 99 68 101 58 100 44 72 7...

Test 41

Verdict:

input
200 84
773442532 122816 137572579 324...

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

user output
64 1 12 25 14 20 9 32 16 31 28...

Test 42

Verdict:

input
200 88
198730372 27838076 590195590 4...

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

user output
14 1 50 36 40 34 24 24 10 15 6...

Test 43

Verdict:

input
200 111
75940263 760367935 901888417 3...

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

user output
8 84 99 35 13 60 69 106 49 107...

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:

input
200 45
59249204 934941692 892631472 2...

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

user output
1 42 40 4 9 45 16 1 24 11 33 9...

Test 46

Verdict:

input
200 179
356460601 224848374 881788059 ...

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

user output
53 33 162 8 4 60 15 112 14 98 ...

Test 47

Verdict:

input
200 16
244103474 837431431 342493822 ...

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

user output
1 14 1 3 11 4 1 5 1 4 1 1 3 1 ...

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:

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
1 2 2 2 1 1 1 1 1 1 3 1 1 1 1 ...

Test 50

Verdict:

input
500 275
636562060 767928734 906523441 ...

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

user output
170 213 250 172 253 153 251 11...

Test 51

Verdict:

input
500 209
773442532 122816 137572579 324...

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

user output
157 1 23 63 29 49 16 79 36 77 ...

Test 52

Verdict:

input
500 218
198730372 27838076 590195590 4...

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

user output
29 3 115 88 98 82 56 58 23 32 ...

Test 53

Verdict:

input
500 276
75940263 760367935 901888417 3...

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

user output
17 203 248 83 30 145 161 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:

input
500 111
59249204 934941692 892631472 2...

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

user output
1 100 94 8 25 108 39 2 55 29 7...

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:

input
500 39
244103474 837431431 342493822 ...

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

user output
1 23 1 4 17 6 1 8 1 7 1 1 4 1 ...

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:

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
1 2 2 2 1 1 1 1 1 1 6 1 1 1 1 ...