Submission #1725658
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef map<int,int>::iterator mit; typedef vector<int>::iterator vit; ll a[211][211]; int h, w; ll dp[402][202][202]; void amax(ll &x, ll y) { x=max(x,y); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>h>>w; for(int i = 1; i <= h; i++) { for(int j = 1; j <= w; j++) { cin>>a[i][j]; } } for(int i = 2; i <= h + w; i++) { for(int j = 1; j <= h; j++) { for(int k = 1; k <= h; k++) { if(j>=i||k>=i) continue; if(i-j>w||i-k>w) continue; dp[i][j][k] = max(max(max(dp[i-1][j-1][k-1], dp[i-1][j][k-1]), dp[i-1][j-1][k]), dp[i-1][j][k]); dp[i][j][k] += a[j][i-j] + a[k][i-k]; if(j==k) dp[i][j][k]-=a[j][i-j]; } } } cout << dp[h+w][h][h] << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | D - Souvenirs |
User | vjudge5 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1216 Byte |
Status | AC |
Exec Time | 70 ms |
Memory | 125568 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | Subtask4 | Subtask5 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 80 / 80 | 120 / 120 | 150 / 150 | 200 / 200 | ||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt |
Subtask1 | sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt |
Subtask2 | sample_1.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt |
Subtask3 | sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt |
Subtask4 | sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt |
Subtask5 | sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub5_in1.txt, sub5_in2.txt, sub5_in3.txt, sub5_in4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 2 ms | 2304 KB |
sub1_in1.txt | AC | 1 ms | 256 KB |
sub1_in2.txt | AC | 1 ms | 256 KB |
sub1_in3.txt | AC | 3 ms | 2432 KB |
sub1_in4.txt | AC | 2 ms | 2304 KB |
sub2_in1.txt | AC | 1 ms | 256 KB |
sub2_in2.txt | AC | 2 ms | 2304 KB |
sub2_in3.txt | AC | 2 ms | 2304 KB |
sub2_in4.txt | AC | 2 ms | 2304 KB |
sub3_in1.txt | AC | 2 ms | 2304 KB |
sub3_in2.txt | AC | 2 ms | 4352 KB |
sub3_in3.txt | AC | 2 ms | 4352 KB |
sub3_in4.txt | AC | 2 ms | 4352 KB |
sub4_in1.txt | AC | 2 ms | 6528 KB |
sub4_in2.txt | AC | 5 ms | 12672 KB |
sub4_in3.txt | AC | 5 ms | 18816 KB |
sub4_in4.txt | AC | 5 ms | 18816 KB |
sub5_in1.txt | AC | 8 ms | 31104 KB |
sub5_in2.txt | AC | 20 ms | 64000 KB |
sub5_in3.txt | AC | 70 ms | 125568 KB |
sub5_in4.txt | AC | 70 ms | 125568 KB |