Submission #289011

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
289011	2020-09-02T09:30:41 Z	phillip	Rectangles (IOI19_rect)	C++14	37 / 100	5000 ms	46996 KB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define fast cin.tie(0);cout.tie(0);
#define order ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);
#define pb push_back
using namespace std;
int n,m,a[2509][2509],mxx[2509][2509],my[2509];
int rec(int x,int y,int x2,int y2)
{
    for(int i=x;i<=x2;i++)
    {
        int mx=mxx[i][y2];
        if(mx>=a[i][y-1]||mx>=a[i][y2+1])return 0;
    }

    for(int j=y;j<=y2;j++)
    {
        int mx=my[j];
        if(mx>=a[x-1][j]||mx>=a[x2+1][j])return 0;
    }
    return 1;
}
ll check(int x,int y)
{
    ll ret=0;
    for(int i=x;i<n-1;i++)
    {
        mxx[i][y-1]=0;
        for(int j=y;j<m-1;j++)
        {
            mxx[i][j]=max(mxx[i][j-1],a[i][j]);
            if(i==x)my[j]=a[i][j];
            else my[j]=max(my[j],a[i][j]);
            if(rec(x,y,i,j))ret++;
        }
    }
    return ret;
}
ll ans;
long long count_rectangles(std::vector<std::vector<int> > aa)
{
    n=aa.size();m=aa[0].size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)a[i][j]=aa[i][j];
    }
    for(int i=1;i<n-1;i++)
    {
        for(int j=1;j<m-1;j++)
        {
            ans+=check(i,j);
        }
    }
    return ans;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	512 KB	Output is correct
20	Correct	1 ms	640 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	61 ms	1024 KB	Output is correct
18	Correct	64 ms	1024 KB	Output is correct
19	Correct	63 ms	1024 KB	Output is correct
20	Correct	45 ms	1024 KB	Output is correct
21	Correct	44 ms	1024 KB	Output is correct
22	Correct	46 ms	1024 KB	Output is correct
23	Correct	46 ms	1124 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	0 ms	384 KB	Output is correct
27	Correct	1 ms	512 KB	Output is correct
28	Correct	1 ms	640 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	61 ms	1024 KB	Output is correct
18	Correct	64 ms	1024 KB	Output is correct
19	Correct	63 ms	1024 KB	Output is correct
20	Correct	45 ms	1024 KB	Output is correct
21	Correct	44 ms	1024 KB	Output is correct
22	Correct	46 ms	1024 KB	Output is correct
23	Correct	46 ms	1124 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	2483 ms	2680 KB	Output is correct
26	Correct	2473 ms	2808 KB	Output is correct
27	Correct	2449 ms	2792 KB	Output is correct
28	Correct	1699 ms	2808 KB	Output is correct
29	Correct	1728 ms	2744 KB	Output is correct
30	Correct	1780 ms	2780 KB	Output is correct
31	Correct	1876 ms	2792 KB	Output is correct
32	Correct	1719 ms	2764 KB	Output is correct
33	Correct	1 ms	384 KB	Output is correct
34	Correct	0 ms	384 KB	Output is correct
35	Correct	1 ms	512 KB	Output is correct
36	Correct	1 ms	640 KB	Output is correct
37	Correct	1 ms	384 KB	Output is correct

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	61 ms	1024 KB	Output is correct
18	Correct	64 ms	1024 KB	Output is correct
19	Correct	63 ms	1024 KB	Output is correct
20	Correct	45 ms	1024 KB	Output is correct
21	Correct	44 ms	1024 KB	Output is correct
22	Correct	46 ms	1024 KB	Output is correct
23	Correct	46 ms	1124 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	2483 ms	2680 KB	Output is correct
26	Correct	2473 ms	2808 KB	Output is correct
27	Correct	2449 ms	2792 KB	Output is correct
28	Correct	1699 ms	2808 KB	Output is correct
29	Correct	1728 ms	2744 KB	Output is correct
30	Correct	1780 ms	2780 KB	Output is correct
31	Correct	1876 ms	2792 KB	Output is correct
32	Correct	1719 ms	2764 KB	Output is correct
33	Execution timed out	5061 ms	14072 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	384 KB	Output is correct
2	Correct	15 ms	384 KB	Output is correct
3	Correct	21 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	21 ms	384 KB	Output is correct
6	Correct	14 ms	384 KB	Output is correct
7	Correct	14 ms	384 KB	Output is correct
8	Correct	14 ms	384 KB	Output is correct
9	Correct	14 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Execution timed out	5056 ms	46996 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	1 ms	512 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	61 ms	1024 KB	Output is correct
18	Correct	64 ms	1024 KB	Output is correct
19	Correct	63 ms	1024 KB	Output is correct
20	Correct	45 ms	1024 KB	Output is correct
21	Correct	44 ms	1024 KB	Output is correct
22	Correct	46 ms	1024 KB	Output is correct
23	Correct	46 ms	1124 KB	Output is correct
24	Correct	13 ms	1024 KB	Output is correct
25	Correct	2483 ms	2680 KB	Output is correct
26	Correct	2473 ms	2808 KB	Output is correct
27	Correct	2449 ms	2792 KB	Output is correct
28	Correct	1699 ms	2808 KB	Output is correct
29	Correct	1728 ms	2744 KB	Output is correct
30	Correct	1780 ms	2780 KB	Output is correct
31	Correct	1876 ms	2792 KB	Output is correct
32	Correct	1719 ms	2764 KB	Output is correct
33	Execution timed out	5061 ms	14072 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Submission #289011

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 7.0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 0 / 22.0

Subtask #5 10.0 / 10.0

Subtask #6 0 / 13.0

Subtask #7 0 / 28.0

Subtask #1
8.0 / 8.0

Subtask #2
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 22.0

Subtask #5
10.0 / 10.0

Subtask #6
0 / 13.0

Subtask #7
0 / 28.0