Task: | ratar |
Sender: | Hansuzu |
Submission time: | 2016-07-27 15:44:07 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 100 |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.06 s | details |
#3 | ACCEPTED | 0.04 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.06 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.08 s | details |
#9 | ACCEPTED | 0.18 s | details |
#10 | ACCEPTED | 0.32 s | details |
#11 | ACCEPTED | 0.32 s | details |
#12 | ACCEPTED | 0.31 s | details |
#13 | ACCEPTED | 0.35 s | details |
Compiler report
input/code.cpp: In function 'void calc(int, int, int, int)': input/code.cpp:44:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=1; i<sms1[x1][y1].size(); ++i){ ^ input/code.cpp:50:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=1; i<sms2[x2][y2].size(); ++i){ ^ input/code.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] while (i1<s1.size() && i2<s2.size()){ ^ input/code.cpp:56:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] while (i1<s1.size() && i2<s2.size()){ ^
Code
#include <iostream>#include <vector>#include <algorithm>#define MP make_pair#define F first#define S secondusing namespace std;int N;int tbl[55][55];int sm[55][55];int csm(int x1, int y1, int x2, int y2){return sm[x2][y2]-sm[x1-1][y2]-sm[x2][y1-1]+sm[x1-1][y1-1];}vector<int> sms1[55][55];vector<int> sms2[55][55];void clrsms(){for (int i=0; i<55; ++i)for (int j=0; j<55; ++j)for (int s=0; s<2552; ++s)sms1[i][j].clear(), sms2[i][j].clear();}long long ans;vector<pair<int, int> > s1;vector<pair<int, int> > s2;void calc(int x1, int y1, int x2, int y2){sort(sms1[x1][y1].begin(), sms1[x1][y1].end());sort(sms2[x2][y2].begin(), sms2[x2][y2].end());s1.clear(); s2.clear();s1.push_back(MP(sms1[x1][y1][0], 1));for (int i=1; i<sms1[x1][y1].size(); ++i){if (s1[s1.size()-1].F!=sms1[x1][y1][i]) s1.push_back(MP(sms1[x1][y1][i], 1));else ++s1[s1.size()-1].S;}s2.push_back(MP(sms2[x2][y2][0], 1));for (int i=1; i<sms2[x2][y2].size(); ++i){if (s2[s2.size()-1].F!=sms2[x2][y2][i]) s2.push_back(MP(sms2[x2][y2][i], 1));else ++s2[s2.size()-1].S;}int i1=0; int i2=0;while (i1<s1.size() && i2<s2.size()){if (s1[i1].F<s2[i2].F) ++i1;else if (s2[i2].F<s1[i1].F) ++i2;else{ans+=s1[i1].S*s2[i2].S;++i1; ++i2;}}}int main(){cin >>N;for (int i=1; i<=N; ++i){for (int j=1; j<=N; ++j){cin >> tbl[i][j];}}for (int i=1; i<=N; ++i){for (int j=1; j<=N; ++j){sm[i][j]=tbl[i][j]+sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];}}for (int x1=1; x1<=N; ++x1){for (int y1=1; y1<=N; ++y1){for (int x2=x1; x2<=N; ++x2){for (int y2=y1; y2<=N; ++y2){int smi=csm(x1, y1, x2, y2);sms1[x1][y1].push_back(smi);sms2[x2][y2].push_back(smi);}}}}for (int x=1; x<N; ++x){for (int y=1; y<N; ++y){calc(x+1, y+1, x, y);}}clrsms();for (int x1=1; x1<=N; ++x1){for (int y1=1; y1<=N; ++y1){for (int x2=x1; x2<=N; ++x2){for (int y2=y1; y2<=N; ++y2){int smi=csm(x1, y1, x2, y2);sms1[x1][y2].push_back(smi);sms2[x2][y1].push_back(smi);}}}}for (int x=1; x<N; ++x){for (int y=2; y<=N; ++y){calc(x+1, y-1, x, y);}}cout << ans << "\n";}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
3
1 2 3 2 3 4 3 4 8 |
correct output |
---|
7 |
user output |
---|
7 |
Test 2
Verdict: ACCEPTED
input |
---|
4
-1 -1 -1 -1 1 2 3 4 1 2 3 4 1 2 3 4 |
correct output |
---|
10 |
user output |
---|
10 |
Test 3
Verdict: ACCEPTED
input |
---|
5
-1 -1 -1 -1 -1 -2 -2 -2 -2 -2 -3 -3 -3 -3 -3 -4 -4 -4 -4 -4 ... |
correct output |
---|
36 |
user output |
---|
36 |
Test 4
Verdict: ACCEPTED
input |
---|
2
1 -1 -1 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 5
Verdict: ACCEPTED
input |
---|
5
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ... |
correct output |
---|
380 |
user output |
---|
380 |
Test 6
Verdict: ACCEPTED
input |
---|
10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 ... |
correct output |
---|
7354 |
user output |
---|
7354 |
Test 7
Verdict: ACCEPTED
input |
---|
10
420 425 490 727 888 391 514 82... |
correct output |
---|
5 |
user output |
---|
5 |
Test 8
Verdict: ACCEPTED
input |
---|
31
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
667480 |
user output |
---|
667480 |
Test 9
Verdict: ACCEPTED
input |
---|
41
475 533 -726 -189 401 -389 667... |
correct output |
---|
17456 |
user output |
---|
17456 |
Test 10
Verdict: ACCEPTED
input |
---|
49
495 -512 159 -874 751 -817 567... |
correct output |
---|
48443 |
user output |
---|
48443 |
Test 11
Verdict: ACCEPTED
input |
---|
49
521 -51 -778 -977 955 -172 695... |
correct output |
---|
39082 |
user output |
---|
39082 |
Test 12
Verdict: ACCEPTED
input |
---|
50
500 500 500 500 500 500 500 50... |
correct output |
---|
4236645 |
user output |
---|
4236645 |
Test 13
Verdict: ACCEPTED
input |
---|
50
933 -493 -881 936 -889 -922 -5... |
correct output |
---|
37917 |
user output |
---|
37917 |