oj.uz

Submission #385762

# Submission time Handle Problem Language Result Execution time Memory
385762 2021-04-04T23:26:55 Z taulant Jelly Flavours (IOI20_jelly) C++17
0 / 100
 267 ms 148076 KB 
#include<bits/stdc++.h>
using namespace std;
typedef array<int, 2> pii;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){
 int n = a.size();
 vector<pii> c(n);
 for(int i = 0; i < n; ++i) c[i] = {a[i], b[i]};
 sort(c.begin(), c.end());
 vector<vector<int>> v(n+1, vector<int>(x+1)), w(n+1, vector<int>(y+1));
 // v: buy i cheapest jelly, given money spent in a, find min extra cost in b
 for(int i = 1; i <= n; ++i){
  for(int j = 0; j <= x; ++j){
   v[i][j] = v[i-1][j] + c[i-1][1];
   if(j >= c[i][0]) v[i][j] = min(v[i][j], v[i-1][j-c[i-1][0]]);
  }
 }
 // w: buy in b jelly that would be expensive in a, find max jelly
 for(int i = n-1; i >= 0; --i){
  for(int j = 0; j <= y; ++j){
   w[i][j] = w[i+1][j];
   if(j >= c[i][1]) v[i][j] = max(v[i][j], v[i+1][j-c[i+1][1]]+1);
  }
 }
 int ans = 0;
 for(int i = 0; i <= n; ++i){
  int yy = y - v[i][x];
  if(yy >= 0) ans = max(ans, i + w[i][yy]);
 }
 return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 13548 KB 1st lines differ - on the 1st token, expected: '689', found: '1949'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 81900 KB 1st lines differ - on the 1st token, expected: '62', found: '1936'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 79724 KB Output is correct
2 Correct 145 ms 141548 KB Output is correct
3 Correct 142 ms 140652 KB Output is correct
4 Correct 186 ms 148076 KB Output is correct
5 Runtime error 267 ms 144580 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
2 Halted 0 ms 0 KB -