QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #187375 | #3005. Monotony | SolitaryDream# | TL | 2599ms | 213732kb | C++17 | 1.9kb | 2023-09-24 16:43:13 | 2023-09-24 16:43:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=21;
int n,m,a[N][N],go[N][N];
vector<int> st[N];
bool vis[N][1<<N];
int f[N][1<<N];
vector<int> ve[1<<N];
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%lld",&a[i][j]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=0;k<m;k++)
if(a[i][k]<a[j][k])
go[i][j]|=1<<k;
int ans=0;
for(int S=1;S<(1<<m);S++)
{
for(int i=0;i<n;i++)
{
bool ok=1;
vector<int>v;
for(int j=0;j<m;j++)
if(S>>j&1)
v.push_back(a[i][j]);
if(v.size()>=2)
{
for(int j=2;j<v.size();j++)
ok&=(v[0]<v[1])==(v[j-1]<v[j]);
}
if(!ok)
{
for(auto x:st[i])
vis[i][x]=0,f[i][x]=0;
st[i].clear();
continue;
}
for(int j=i+1;j<n;j++)
ve[go[i][j]&S].push_back(j);
for(int j=i+1;j<n;j++)
{
f[j][go[i][j]&S]++;
if(!vis[j][go[i][j]&S])
vis[j][go[i][j]&S]=1,st[j].push_back(go[i][j]&S);
}
for(auto x:st[i])
{
ans+=f[i][x];
for(auto j:ve[x])
{
f[j][x]+=f[i][x];
if(!vis[j][x])
st[j].push_back(x),vis[j][x]=1;
}
vis[i][x]=0;
f[i][x]=0;
}
for(int j=i+1;j<n;j++)
ve[go[i][j]&S].clear();
st[i].clear();
ans++;
}
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 175ms
memory: 103168kb
input:
13 17 155 221 29 114 165 175 120 107 27 134 125 116 11 56 100 20 15 88 128 38 111 198 212 173 136 44 164 64 150 83 19 93 197 194 219 25 16 50 2 55 151 34 163 76 217 209 141 174 80 144 159 60 156 54 149 97 28 102 145 26 35 188 160 65 152 135 6 21 8 62 195 70 127 30 171 205 147 177 210 117 10 103 161 ...
output:
40490
result:
ok answer is '40490'
Test #2:
score: 0
Accepted
time: 17ms
memory: 87228kb
input:
17 13 41 205 162 42 35 147 143 185 89 176 4 103 181 85 115 59 2 182 190 20 142 97 172 31 211 101 154 62 119 82 16 117 1 157 72 3 149 216 21 188 49 202 77 161 160 169 46 79 133 50 113 91 30 71 156 193 92 29 54 187 111 199 80 22 17 209 122 138 127 135 81 53 86 158 145 109 56 6 150 40 15 212 10 186 32 ...
output:
35799
result:
ok answer is '35799'
Test #3:
score: 0
Accepted
time: 7ms
memory: 53796kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 3ms
memory: 54340kb
input:
1 2 1 2
output:
3
result:
ok answer is '3'
Test #5:
score: 0
Accepted
time: 3ms
memory: 54080kb
input:
1 2 2 1
output:
3
result:
ok answer is '3'
Test #6:
score: 0
Accepted
time: 167ms
memory: 54548kb
input:
1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
output:
1048575
result:
ok answer is '1048575'
Test #7:
score: 0
Accepted
time: 7ms
memory: 56052kb
input:
2 1 1 2
output:
3
result:
ok answer is '3'
Test #8:
score: 0
Accepted
time: 3ms
memory: 55716kb
input:
2 1 2 1
output:
3
result:
ok answer is '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 56148kb
input:
2 2 1 2 3 4
output:
9
result:
ok answer is '9'
Test #10:
score: 0
Accepted
time: 3ms
memory: 56788kb
input:
2 2 1 3 4 2
output:
9
result:
ok answer is '9'
Test #11:
score: 0
Accepted
time: 7ms
memory: 56500kb
input:
2 2 2 1 4 3
output:
9
result:
ok answer is '9'
Test #12:
score: 0
Accepted
time: 7ms
memory: 55008kb
input:
2 2 3 2 4 1
output:
9
result:
ok answer is '9'
Test #13:
score: 0
Accepted
time: 7ms
memory: 56272kb
input:
2 2 4 3 2 1
output:
9
result:
ok answer is '9'
Test #14:
score: 0
Accepted
time: 4ms
memory: 60860kb
input:
4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
output:
225
result:
ok answer is '225'
Test #15:
score: 0
Accepted
time: 4ms
memory: 59584kb
input:
4 4 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13
output:
225
result:
ok answer is '225'
Test #16:
score: 0
Accepted
time: 0ms
memory: 60136kb
input:
4 4 4 5 1 3 11 6 13 10 16 2 9 8 14 15 12 7
output:
110
result:
ok answer is '110'
Test #17:
score: 0
Accepted
time: 4ms
memory: 93276kb
input:
20 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
output:
1048575
result:
ok answer is '1048575'
Test #18:
score: 0
Accepted
time: 1060ms
memory: 139568kb
input:
20 19 180 179 178 177 176 175 174 173 172 190 189 188 187 186 185 184 183 182 181 161 160 159 158 157 156 155 154 153 171 170 169 168 167 166 165 164 163 162 142 141 140 139 138 137 136 135 134 152 151 150 149 148 147 146 145 144 143 123 122 121 120 119 118 117 116 115 133 132 131 130 129 128 127 12...
output:
3485104
result:
ok answer is '3485104'
Test #19:
score: 0
Accepted
time: 1047ms
memory: 181788kb
input:
20 19 9 8 7 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 10 28 27 26 25 24 23 22 21 20 38 37 36 35 34 33 32 31 30 29 47 46 45 44 43 42 41 40 39 57 56 55 54 53 52 51 50 49 48 66 65 64 63 62 61 60 59 58 76 75 74 73 72 71 70 69 68 67 85 84 83 82 81 80 79 78 77 95 94 93 92 91 90 89 88 87 86 104 103 102 101 10...
output:
1702885800
result:
ok answer is '1702885800'
Test #20:
score: 0
Accepted
time: 2599ms
memory: 213732kb
input:
20 19 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 13...
output:
1125119902
result:
ok answer is '1125119902'
Test #21:
score: -100
Time Limit Exceeded
input:
20 20 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...