# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
191344 | 2020-01-14T20:04:40 Z | Ruxandra985 | Kitchen (BOI19_kitchen) | C++14 | 27 ms | 1148 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 | 3 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 0 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Incorrect | 2 ms | 376 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 0 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Incorrect | 2 ms | 376 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 992 KB | Output is correct |
2 | Correct | 22 ms | 776 KB | Output is correct |
3 | Correct | 26 ms | 760 KB | Output is correct |
4 | Correct | 27 ms | 1148 KB | Output is correct |
5 | Incorrect | 27 ms | 1016 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 6 ms | 504 KB | Output is correct |
5 | Incorrect | 2 ms | 376 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 0 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Incorrect | 2 ms | 376 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |