#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 MAXN 300
#define MAXY 9 // Y[i] + 1
ll n,m;
long long arr[MAXN+1][MAXY+1];
long long dp[MAXN+1][MAXY+1][MAXY+1];
long long s[MAXN+1][MAXY+1];
void tabb(ll n) {
for (ll i=0; i<n; i++) cout<<"\t";
}
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];
}
}
long long solve(ll i, ll j, ll k){
// dbg3(i,j,k);
//base case
if (i < 0) return 0;
//general case
if (dp[i][j][k] == -1){
long long ans = 0,c;
for (ll y =0; y<=j; y++){
// dbg(y);
c = solve(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 = solve(i-1,k,y);
ans = max(ans, c);
}
dp[i][j][k] = ans;
}
return dp[i][j][k];
}
long long init_solve(){
ll b;
for (ll i=0;i<n;i++){
if (i == 0) b = 0;
else b = -1;
for (ll j =0;j <=MAXY; j++){
for (ll k =0; k<=MAXY; k++){
dp[i][j][k] = b;
}
}
}
long long ans =0 ;
for (ll i=0; i<=MAXY; i++){
for (ll j =0; j<=MAXY; j++){
ans = max(ans, solve(n-1,i,j));
}
}
return ans;
}
long long max_weights(int N, int M, vi X, vi Y, vi W) {
n= N, 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-1];
}
}
// printArr2D(s,n,MAXY,"s");
// dbg3(calc(0,3,5), calc(2, 1, 4), calc(4, 3, 8));
long long ans = init_solve();
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
5584 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
5584 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
