oj.uz

Submission #819114

# Submission time Handle Problem Language Result Execution time Memory
819114 2023-08-10T08:04:19 Z cig32 Akcija (COCI21_akcija) C++17
50 / 110
 262 ms 160088 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long 
#define double long double
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
bool cmp(pair<int, int> x, pair<int, int> y) {
  return x.second < y.second;
}
void solve(int tc) {
  int n, k;
  cin >> n >> k;
  pair<int, int> p[n+1];
  for(int i=1; i<=n; i++) cin >> p[i].first >> p[i].second;
  sort(p+1, p+1+n, cmp);
  int m = ceil(sqrt(k));
  int dp[n+1][n+1][m+1];
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      dp[0][i][j] = 1e18;
    }
  }
  dp[0][0][1] = 0;
  for(int i=2; i<=m; i++) dp[0][0][i] = 1e18;
  for(int i=1; i<=n; i++) {
    for(int j=0; j<i; j++) {
      for(int l=1; l<=m; l++) {
        dp[i][j][l] = 1e18;
      }
    }
    int opt[m+1];
    for(int j=1; j<=m; j++) opt[j] = 1e18;
    for(int j=0; j<i; j++) {
      int res[m+1];
      int p1 = 1, p2 = 1;
      for(int l=1; l<=m; l++) {
        if(dp[i-1][j][p1] < opt[p2]) {
          res[l] = dp[i-1][j][p1++];
        }
        else {
          res[l] = opt[p2++];
        }
      }
      for(int l=1; l<=m; l++) {
        opt[l] = res[l];
      }
    }
    for(int j=i; j<=n; j++) {
      if(p[j].second >= i) {
        for(int l=1; l<=m; l++) dp[i][j][l] = opt[l] + p[j].first;
      }
      else {
        for(int l=1; l<=m; l++) dp[i][j][l] = 1e18;
      }
      int res[m+1];
      int p1 = 1, p2 = 1;
      for(int l=1; l<=m; l++) {
        if(dp[i-1][j][p1] < opt[p2]) {
          res[l] = dp[i-1][j][p1++];
        }
        else {
          res[l] = opt[p2++];
        }
      }
      for(int l=1; l<=m; l++) {
        opt[l] = res[l];
      }
    }
  }
  vector<pair<int, int> > sol;
  for(int i=n; i>=0; i--) {
    vector<int> v;
    for(int j=i; j<=n; j++) {
      for(int l=1; l<=m; l++) {
        if(dp[i][j][l] <= 1e13) v.push_back(dp[i][j][l]);
      }
    }
    sort(v.begin(), v.end());
    for(int x: v) {
      sol.push_back({i, x});
    }
  }
  for(int i=0; i<k; i++) {
    cout << sol[i].first << ' ' << sol[i].second << '\n';
  }
  
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 91056 KB Output is correct
2 Correct 106 ms 95968 KB Output is correct
3 Correct 113 ms 86196 KB Output is correct
4 Correct 90 ms 84828 KB Output is correct
5 Correct 107 ms 94800 KB Output is correct
6 Correct 60 ms 51816 KB Output is correct
7 Correct 48 ms 62804 KB Output is correct
8 Correct 44 ms 53896 KB Output is correct
9 Correct 57 ms 52364 KB Output is correct
10 Correct 64 ms 63700 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 91056 KB Output is correct
2 Correct 106 ms 95968 KB Output is correct
3 Correct 113 ms 86196 KB Output is correct
4 Correct 90 ms 84828 KB Output is correct
5 Correct 107 ms 94800 KB Output is correct
6 Correct 60 ms 51816 KB Output is correct
7 Correct 48 ms 62804 KB Output is correct
8 Correct 44 ms 53896 KB Output is correct
9 Correct 57 ms 52364 KB Output is correct
10 Correct 64 ms 63700 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 128 ms 91044 KB Output is correct
15 Correct 155 ms 95952 KB Output is correct
16 Correct 105 ms 86216 KB Output is correct
17 Correct 109 ms 84868 KB Output is correct
18 Correct 124 ms 94956 KB Output is correct
19 Correct 40 ms 51788 KB Output is correct
20 Correct 53 ms 62796 KB Output is correct
21 Correct 43 ms 53832 KB Output is correct
22 Correct 42 ms 52352 KB Output is correct
23 Correct 66 ms 63656 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 152620 KB Output is correct
2 Correct 262 ms 160088 KB Output is correct
3 Correct 200 ms 145524 KB Output is correct
4 Correct 207 ms 143484 KB Output is correct
5 Correct 244 ms 158316 KB Output is correct
6 Correct 71 ms 77456 KB Output is correct
7 Correct 94 ms 94048 KB Output is correct
8 Correct 69 ms 80760 KB Output is correct
9 Correct 76 ms 78864 KB Output is correct
10 Correct 106 ms 99376 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 91056 KB Output is correct
2 Correct 106 ms 95968 KB Output is correct
3 Correct 113 ms 86196 KB Output is correct
4 Correct 90 ms 84828 KB Output is correct
5 Correct 107 ms 94800 KB Output is correct
6 Correct 60 ms 51816 KB Output is correct
7 Correct 48 ms 62804 KB Output is correct
8 Correct 44 ms 53896 KB Output is correct
9 Correct 57 ms 52364 KB Output is correct
10 Correct 64 ms 63700 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 128 ms 91044 KB Output is correct
15 Correct 155 ms 95952 KB Output is correct
16 Correct 105 ms 86216 KB Output is correct
17 Correct 109 ms 84868 KB Output is correct
18 Correct 124 ms 94956 KB Output is correct
19 Correct 40 ms 51788 KB Output is correct
20 Correct 53 ms 62796 KB Output is correct
21 Correct 43 ms 53832 KB Output is correct
22 Correct 42 ms 52352 KB Output is correct
23 Correct 66 ms 63656 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 229 ms 152620 KB Output is correct
28 Correct 262 ms 160088 KB Output is correct
29 Correct 200 ms 145524 KB Output is correct
30 Correct 207 ms 143484 KB Output is correct
31 Correct 244 ms 158316 KB Output is correct
32 Correct 71 ms 77456 KB Output is correct
33 Correct 94 ms 94048 KB Output is correct
34 Correct 69 ms 80760 KB Output is correct
35 Correct 76 ms 78864 KB Output is correct
36 Correct 106 ms 99376 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 320 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Incorrect 2 ms 596 KB Output isn't correct
41 Halted 0 ms 0 KB -