Submission #67405

#TimeUsernameProblemLanguageResultExecution timeMemory
67405quoriessMaxcomp (info1cup18_maxcomp)C++14
100 / 100
356 ms47136 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int lli; typedef pair<int,int> pii; vector<vector<int> > matris; int n,m; typedef pair<lli,pii> data; const int MAXN=1e3+5, MAXM=1e3+5; vector<pii> komsu(int a,int b){ vector<pii> don; for (int i = -1; i < 2; i++) { for (int j = -1; j < 2; j++) { if(a+i>=0 && a+i< n && b+j<m && b+j>=0 && (i!=0||j!=0) && (i==0 || j==0)){ don.push_back({a+i,b+j}); } } } return don; } /* 3 3 1 7 5 3 6 9 4 8 3 * */ void rotate90(vector<vector<int> >& cevir,vector<vector<int> >& yeni){ /* 1 4 7 8 2 5 9 * 3 6 - | * * * 3 2 1 6 5 4 - 9 7 | * 8 0,0 -> 0,2 1,0 -> 0,1 2,0 -> 0,0 ters çevir, n-ikinci * */ for (int i = 0; i < (int)cevir.size(); i++) { for (int j = 0; j < (int)cevir[0].size(); j++) { yeni[j][cevir.size()-i-1]=cevir[i][j]; } } } /* min en sağ aşağıda olsun: value+k.y+k.x max-min-(-max.x+-max.y+min.x+min.y+1) * * */ int ans=-1e7; void solve(vector<vector<int> >& par){ vector<vector<int> > dp(par.size(),vector<int>(par[0].size(),-1e6)); for (int i = 0; i < par.size(); i++) { for (int j = 0; j < par[0].size(); j++) { dp[i][j]=max(dp[i][j],par[i][j]+i+j); if(i!=0)dp[i][j]=max(dp[i][j],dp[i-1][j]); if(j!=0)dp[i][j]=max(dp[i][j],dp[i][j-1]); } } for (int i = 0; i < par.size(); i++) { for (int j = 0; j < par[0].size(); j++) { ans=max(ans,dp[i][j]-par[i][j]-i-j-1); //cout << ans<<"\n"; } } } void yazdir(vector<vector<int> > matris){ for (int i = 0; i < (int) matris.size(); i++) { for (int j = 0; j<(int) matris[0].size() ; j++) { cout<<matris[i][j]<<" "; } cout <<"\n"; } } /* 4 5 8 7 6 9 16 3 12 19 33 21 9 9 9 9 9 15 14 13 11 17 1 4 2 4 * */ int main(){ cin>>n>>m; matris=vector<vector<int> >(n,vector<int>(m,0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d",&matris[i][j]); } } vector<vector<int> > eski,yeni,yeni2,yeni3; for(int i=0;i<n;i++){ eski.push_back(vector<int>()); for(int j=0;j<m;j++){ eski[i].push_back(matris[i][j]); } } solve(matris); yeni=vector<vector<int> >(matris[0].size(),vector<int>(matris.size())); rotate90(matris,yeni); solve(yeni); yeni2=vector<vector<int> >(yeni[0].size(),vector<int>(yeni.size())); rotate90(yeni,yeni2); solve(yeni2); yeni3=vector<vector<int> >(yeni2[0].size(),vector<int>(yeni2.size())); rotate90(yeni2,yeni3); solve(yeni3); /*for (int i = 0; i < 4; i++) { //cout <<"iter: "<<i<<"\n"; solve(eski); //cout << "ans: "<<ans<<" "; //cout <<"\n"; //yazdir(eski); rotate90(eski,yeni); //yazdir(yeni); eski=yeni; }*/ cout <<ans<<"\n"; return 0; }

Compilation message (stderr)

maxcomp.cpp: In function 'void solve(std::vector<std::vector<int> >&)':
maxcomp.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < par.size(); i++)
                  ~~^~~~~~~~~~~~
maxcomp.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < par[0].size(); j++)
                   ~~^~~~~~~~~~~~~~~
maxcomp.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < par.size(); i++)
                  ~~^~~~~~~~~~~~
maxcomp.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < par[0].size(); j++)
                   ~~^~~~~~~~~~~~~~~
maxcomp.cpp: In function 'int main()':
maxcomp.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matris[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...