# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
191346 | 2020-01-14T20:11:59 Z | Ruxandra985 | Kitchen (BOI19_kitchen) | C++14 | 31 ms | 1016 KB |
#include <bits/stdc++.h> #define DIMN 310 using namespace std; int a[DIMN] , b[DIMN]; int v[DIMN] , tt[DIMN * DIMN] , ok[DIMN * DIMN]; int n , k; int maybe (int sum){ int nod , elem , solved , poz , i , put , outof; nod = sum; elem = 0; while (nod){ v[++elem] = tt[nod]; nod = nod - b[tt[nod]]; } /// v e lista pe care vreau eu sa o am , cu suma fixa sum /// eu la suma asta am maximizat nr de elem distincte solved = 0; int s = 0; for (i=1;i<=elem;i++){ if (b[v[i]] > n) solved++; else s += b[v[i]]; } if (s / n + solved >= k) return 1; return 0; } int main() { FILE *fin = stdin; FILE *fout = stdout; int m , sum , i , val , sol; fscanf (fin,"%d%d%d",&n,&m,&k); sum = 0; for (i=1;i<=n;i++){ fscanf (fin,"%d",&a[i]); sum += a[i]; if (a[i] < k){ fprintf (fout,"Impossible"); return 0; } } sort (a + 1 , a + n + 1); for (i=1;i<=m;i++){ fscanf (fin,"%d",&b[i]); } sort (b + 1 , b + m + 1); /// ai putea face un rucsac asa de idee ok[0] = 1; tt[0] = -1; for (i = 1 ; i <= m ; i++ ){ for (val = 300 * 300 ; val - b[i] >= 0 ; val--){ if (!ok[val] && ok[val - b[i]]){ ok[val] = 1; tt[val] = i; } } } /// 300 ^ 3 sol = 2000000000; for (val = sum ; val <= 300 * 300 ; val++){ if (ok[val] && maybe(val)){ sol = min (sol , val - sum); break; } } if (sol == 2000000000){ fprintf (fout,"Impossible"); } else { fprintf (fout,"%d",sol); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 7 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 7 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 4 ms | 376 KB | Output is correct |
10 | Correct | 4 ms | 504 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 3 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 876 KB | Output is correct |
2 | Correct | 23 ms | 760 KB | Output is correct |
3 | Correct | 27 ms | 632 KB | Output is correct |
4 | Correct | 27 ms | 1016 KB | Output is correct |
5 | Correct | 27 ms | 988 KB | Output is correct |
6 | Correct | 21 ms | 760 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 380 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 7 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 4 ms | 376 KB | Output is correct |
10 | Correct | 4 ms | 504 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 3 ms | 376 KB | Output is correct |
14 | Correct | 26 ms | 876 KB | Output is correct |
15 | Correct | 23 ms | 760 KB | Output is correct |
16 | Correct | 27 ms | 632 KB | Output is correct |
17 | Correct | 27 ms | 1016 KB | Output is correct |
18 | Correct | 27 ms | 988 KB | Output is correct |
19 | Correct | 21 ms | 760 KB | Output is correct |
20 | Correct | 5 ms | 376 KB | Output is correct |
21 | Correct | 5 ms | 376 KB | Output is correct |
22 | Correct | 5 ms | 376 KB | Output is correct |
23 | Correct | 5 ms | 380 KB | Output is correct |
24 | Correct | 2 ms | 376 KB | Output is correct |
25 | Correct | 23 ms | 940 KB | Output is correct |
26 | Correct | 31 ms | 760 KB | Output is correct |
27 | Correct | 16 ms | 504 KB | Output is correct |
28 | Correct | 23 ms | 760 KB | Output is correct |
29 | Correct | 23 ms | 888 KB | Output is correct |
30 | Correct | 27 ms | 1016 KB | Output is correct |