| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 161524 |
2019-11-02T20:39:56 Z |
Ort |
Retro (COCI17_retro) |
C++11 |
|
137 ms |
95844 KB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define mem(a, b) memset(a, (b), sizeof(a))
#define all(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define linf (ll)1e18
#define inf (int)1e9
#define minf 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define mod 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 305
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, m;
int DP[MAX][MAX][MAX];
char MAT[MAX][MAX];
bool isreachable[MAX][MAX];
// testiramo samo za partialy correct
int main() {
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) scanf("%s", MAT[i]+1);
// clock_t z = clock();
for(int i=1;i<=m;i++)
if(MAT[n][i]=='M') {
isreachable[n][i] = true;
break;
}
for(int i=n-1;i>=1;i--)
for(int j=1;j<=m;j++)
isreachable[i][j] |= isreachable[i+1][j] |= isreachable[i+1][j-1] |= isreachable[i+1][j+1];
for(int i=n-1;i>=1;i--)
for(int j=1;j<=m;j++) {
if(!isreachable[i][j]) continue;
for(int k=0;k<300;k++) {
if(MAT[i][j]=='*') {
continue;
}
if(MAT[i][j]=='.') {
DP[i][j][k] = max(DP[i+1][j][k], max(DP[i+1][j-1][k], DP[i+1][j+1][k]));
continue;
}
if(MAT[i][j]=='(' && k>0) {
DP[i][j][k] = max(DP[i+1][j][k-1], max(DP[i+1][j-1][k-1], DP[i+1][j+1][k-1])) + 1;
continue;
}
if(MAT[i][j]==')') {
DP[i][j][k] = max(DP[i+1][j][k+1], max(DP[i+1][j-1][k+1], DP[i+1][j+1][k+1]));
continue;
}
}
}
int best = 0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(!isreachable[i][j]) continue;
best = max(best, DP[i][j][0]);
}
}
cout << best*2 <<"\n";
cout << "()";
// cout << (double)(clock() - z) / CLOCKS_PER_SEC;
return 0;
}
Compilation message
retro.cpp: In function 'int main()':
retro.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
retro.cpp:38:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%s", MAT[i]+1);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Partially correct |
2 ms |
508 KB |
Partially correct |
| 3 |
Partially correct |
2 ms |
504 KB |
Partially correct |
| 4 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
1148 KB |
Output isn't correct |
| 6 |
Incorrect |
12 ms |
5624 KB |
Output isn't correct |
| 7 |
Partially correct |
11 ms |
5496 KB |
Partially correct |
| 8 |
Incorrect |
8 ms |
4600 KB |
Output isn't correct |
| 9 |
Incorrect |
13 ms |
8696 KB |
Output isn't correct |
| 10 |
Incorrect |
17 ms |
11384 KB |
Output isn't correct |
| 11 |
Incorrect |
126 ms |
88312 KB |
Output isn't correct |
| 12 |
Incorrect |
119 ms |
88184 KB |
Output isn't correct |
| 13 |
Partially correct |
62 ms |
44152 KB |
Partially correct |
| 14 |
Incorrect |
60 ms |
43900 KB |
Output isn't correct |
| 15 |
Incorrect |
136 ms |
84512 KB |
Output isn't correct |
| 16 |
Incorrect |
116 ms |
84472 KB |
Output isn't correct |
| 17 |
Incorrect |
119 ms |
83700 KB |
Output isn't correct |
| 18 |
Incorrect |
113 ms |
83576 KB |
Output isn't correct |
| 19 |
Incorrect |
137 ms |
95844 KB |
Output isn't correct |
| 20 |
Incorrect |
136 ms |
95648 KB |
Output isn't correct |
