Submission #97770

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
97770	2019-02-18 11:46:14	igzi	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	193 ms	17144 KiB

maxcomp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define maxN 1005
using namespace std;
int a[maxN][maxN],dp[maxN][maxN],n,m,i,j;
int ans=-1;
int resi(){
int res=-1,i,j,tmp;
for(i=0;i<n;i++){
    for(j=0;j<m;j++){
        tmp=a[i][j]-i-j;
        if(i>0) tmp=min(tmp,dp[i-1][j]);
        if(j>0) tmp=min(tmp,dp[i][j-1]);
        res=max(res,a[i][j]-i-j-tmp-1);
        dp[i][j]=tmp;
    }
}
for(i=n-1;i>=0;i--){
    for(j=m-1;j>=0;j--){
        tmp=a[i][j]+i+j;
        if(i<n-1) tmp=min(tmp,dp[i+1][j]);
        if(j<m-1) tmp=min(tmp,dp[i][j+1]);
        res=max(res,a[i][j]+i+j-tmp-1);
        dp[i][j]=tmp;
    }
}
return res;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40