제출 #1079394

#제출 시각아이디문제언어결과실행 시간메모리
1079394phongTwo Dishes (JOI19_dishes)C++17
10 / 100
2737 ms128488 KiB
#include<bits/stdc++.h> #define ll long long const int nmax = 2e5 + 5, N = 1e5; const ll oo = 1e18 + 1, base = 311; const int lg = 19, M = 10; const ll mod = 998244353, mod2 = 1e9 + 5277; #define pii pair<int, int> #define fi first #define se second #define endl "\n" #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n"; using namespace std; int n, m; struct node{ ll x, y, z; }a[nmax], b[nmax]; map<int, ll> adj[nmax]; ll tree[nmax << 2]; ll dp[2005][2005]; void update(int id, int l, int r, int u, ll val){ if(l > u || r < u) return; if(l == r){ tree[id] = max(tree[id], val); return; } int mid = r + l >> 1; update(id << 1, l, mid, u, val); update(id << 1 |1, mid + 1, r, u, val); tree[id] = max(tree[id << 1], tree[id << 1 | 1]); } int get(int id, int l, int r, int u, int v){ if(l >= u && r <=v) return tree[id]; int mid = r + l >> 1; if(mid < u) return get(id << 1 | 1, mid + 1, r,u, v); if(mid + 1 > v) return get(id << 1, l, mid, u, v); return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("code.inp", "r", stdin); // freopen("code.out", "w", stdout); cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].z, a[i].x += a[i - 1].x; for(int i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].x += b[i - 1].x; // ll ans = 0; // for(int i = 1; i <= n; ++i){ // if(a[i].x <= a[i].y){ // int l = 1, r = m, it = m + 1; // while(l <= r){ // int mid = r + l >> 1; // if(b[mid].x > a[i].y - a[i].x){ // r = mid - 1; // it = mid; // } // else l = mid + 1; // } // ans += a[i].z; //// if(it <= m) adj[i][it] -= a[i].z; // } // } // for(int i = 1; i <= m; ++i){ // // if(b[i].x <= b[i].y){ // int l = 1, r = n, it = n + 1; // while(l <= r){ // int mid = r + l >> 1; // if(a[mid].x > b[i].y - b[i].x){ // r = mid - 1; // it = mid; // } // else l = mid + 1; // } //// cout << i << ' ' << it << endl; // // if(it > n) ans += b[i].z; // else adj[it][i] += b[i].z; // } // } // memset(dp, -63, sizeof dp); // dp[0][0] = 0; for(int i = 0; i <= n; ++i){ for(int j = 0; j <= m; ++j){ // cout << adj[i][j] << ' '; if(j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1] + (a[i].x + b[j].x <= b[j].y) * b[j].z); if(i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j] + (a[i].x + b[j].x <= a[i].y) * a[i].z); // if(j == 1){ // cout << a[i].x + b[j].x <<' ' << b[j].y; // exit(0); // } } } cout << dp[n][m]; } /* 5 10 2 4 1 1 1 2 1 3 1 1 1 100 1 1 1 1 3 */

컴파일 시 표준 에러 (stderr) 메시지

dishes.cpp: In function 'void update(int, int, int, int, long long int)':
dishes.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: In function 'int get(int, int, int, int, int)':
dishes.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: At global scope:
dishes.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...