Submission #615523

#TimeUsernameProblemLanguageResultExecution timeMemory
615523HediChehaidarRemittance (JOI19_remittance)C++17
0 / 100
1 ms316 KiB
#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define dte tuple<double , double , double> using namespace std; const int INF = 1000*1000*1000; // 1 e 9 const int MOD = 1e9 + 7;//998244353 ; const double EPS = 0.000000001; // 1 e -9 const ll inf = (ll)1e18; bool vis[22]; bool ok = true; int n; pll p[22]; void dfs(int pos , ll need){ //cout << pos << " " << need << "\n"; int i = pos; if(vis[pos]) { ok = false; return; } vis[pos] = true; ll cur = p[i].ff - p[i].ss; if(cur >= need) { p[i].ff -= need; return; } ll nxt = (need - max((ll)0 , p[i].ff - p[i].ss) + max((ll)0 , p[i].ss - p[i].ff)) * 2; int id = pos - 1; if(id == -1) id = n - 1; dfs(id , nxt); p[i].ff = p[i].ss; } int main(){ //ifstream fin ("testing.txt"); //ofstream fout ("output.txt"); ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n; if(n > 20) return 0; for(int i = 0 ; i < n ; i++) cin>>p[i].ff>>p[i].ss; for(int i = 0 ; i < n ; i++){ if(p[i].ff < p[i].ss){ memset(vis , 0 , sizeof vis); ok = true; dfs(i , 0); if(!ok) return cout << "No\n",0; } } for(int i = 0 ; i < n ; i++){ if(p[i].ff != p[i].ss) return cout << "No\n",0; } cout << "Yes\n"; return 0; } /* Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD Read the statement CAREFULLY !! Make a GREADY APPROACH !!!! (start from highest / lowest) Make your own TESTS !! Be careful from CORNER CASES ! */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...