제출 #835894

#제출 시각아이디문제언어결과실행 시간메모리
835894ALeonidou메기 농장 (IOI22_fish)C++17
14 / 100
41 ms8892 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; #define ll int #define sz(x) (ll)x.size() #define F first #define S second #define pb push_back #define MID ((l+r)/2) #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; typedef vector <ll> vi; typedef vector <long long > vl; typedef pair <ll,ll> ii; typedef vector <ii> vii; void printVct(vl &v, string s = ""){ cout<<s<<": "; for (ll i=0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } #define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl; #define N 300 #define MAXY 9 // Y[i] + 1 ll n,m; long long arr[N+1][MAXY+1]; long long dp[N+1][MAXY+1][MAXY+1]; long long s[N+1][MAXY+1]; long long calc(ll u, ll l, ll r){ // 0 <= x <= 9 if (u < 0){ cout<<"ERROR!! "<<u<<" "<<l<<" "<<r<<endl<<endl; exit(1); } if (l > r){ cout<<"ERROR!"<<endl; return 0; } l--, r--; if (l == 0){ return s[u][r]; } else{ return s[u][r] - s[u][l-1]; } } void printDP(ll l = 0, ll r = MAXY){ for (ll k=l; k<=r; k++){ cout<<"k: "<<k<<endl; for (ll i = 0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<=MAXY; j++){ cout<<dp[i][j][k]; } cout<<endl; } cout<<endl; } cout<<endl; } long long solve(){ //prep line 0 for (ll j =0; j<=MAXY; j++){ for (ll k =0; k<=MAXY; k++){ dp[0][j][k] = 0; } } //prep line 1 for (ll j =0; j<=MAXY; j++){ for (ll k =0; k<=MAXY; k++){ if (j == k) dp[1][j][k] = 0; else if (j > k){ dp[1][j][k] = calc(0, k+1, j); } else{ dp[1][j][k] = calc(1, j+1, k); } } } // printDP(); //solve for (ll i =2; i<n; i++){ for (ll j = 0; j<=MAXY; j++){ for (ll k =0; k<=MAXY; k++){ long long ans = 0, c; if (j > k){ for (ll y = 0; y<=MAXY; y++){ if (y <= k){ c = dp[i-1][k][y] + calc(i-1,k+1,j); } else if (y < j){ c = dp[i-1][k][y] + calc(i-1,y+1,j); } else{ c = dp[i-1][k][y]; } ans = max(ans, c); } } else{ // j <= k for (ll y = 0; y<=MAXY; y++){ ans = max(ans, dp[i-1][k][y]); } if (j < k){ ans += calc(i, j+1, k); } } dp[i][j][k] = ans; } } } // printDP(); long long ans =0; for (ll i =0; i<n; i++){ for (ll j =0; j<=MAXY; j++){ for (ll k =0; k<=MAXY; k++){ ans = max(ans, dp[i][j][k]); } } } return ans; } long long max_weights(int NN, int M, vi X, vi Y, vi W) { n= NN, m =M; for (ll i =0 ; i<m; i++){ arr[X[i]][Y[i]] = W[i]; } for (ll i =0; i<n; i++){ s[i][0] = arr[i][0]; for (ll j = 1; j< MAXY; j++){ s[i][j] = s[i][j-1] + arr[i][j]; } } // printArr2D(s,n,MAXY,"s"); long long ans = solve(); return ans; } /* 116037261256 216624184325 => our answer is less */
#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...