제출 #835763

#제출 시각아이디문제언어결과실행 시간메모리
835763ALeonidou메기 농장 (IOI22_fish)C++17
0 / 100
41 ms8092 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){ 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; for (ll y =0; y<=j; y++){ c = dp[i-1][k][y] + calc(i-1, max(y,k+1), j); //chek indexes ans=max(ans, c); } for (ll y =j+1; y<=MAXY; y++){ c = dp[i-1][k][y]; ans = max(ans, c); } 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...