이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IZhO14_bank
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug;
int ctPeople, ctNotes;
int p[21], n[21];
pii dp[1<<20];
int main() {
debug = true;
ios_base::sync_with_stdio(false); cin.tie(0);
int i, j, k;
cin >> ctPeople >> ctNotes;
for(i=1;i<=ctPeople; i++) cin >> p[i];
for(j=0;j<ctNotes; j++) cin >> n[j];
int pay = 0;
for(i=1; i<=ctPeople; i++) {
//cout << i << endl;
pay += p[i];
/// find all match that can pay people i
dp[0] = mp(0, i);
for(int match = 1; match < (1<<ctNotes); match++) {
if( dp[match].snd != i) {
if( dp[match].fst != pay - p[i]) dp[match].fst = 0; /// if can not pay 1 ... (i-1) person, then does not work
dp[match].snd = i;
}
for(j=0; j<ctNotes; j++) {
if( (match & (1<<j)) == 0 ) continue;
int pre = match - (1<<j);
if ( ( i==1 && (pre == 0 || dp[pre].fst>0)) || (i>1 && dp[pre].fst>0) ) {
if(dp[pre].fst + n[j] <= pay) {
dp[match] = mp(dp[pre].fst + n[j], i);
//cout << match <<" = " << dp[match].fst << endl;
}
}
}
}
}
bool canpay = false;
for(int match = 0; !canpay && match < (1<<ctNotes); match++) {
if(dp[match].fst == pay && dp[match].snd == ctPeople) canpay = true;
}
if(canpay) cout << "YES" << endl;
else cout << "NO" << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
bank.cpp: In function 'int main()':
bank.cpp:63:15: warning: unused variable 'k' [-Wunused-variable]
63 | int i, j, k;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |