Submission #3421616
Source Code Expand
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define pb push_back
using namespace std;
const int N=305,M=4510005,mod=1000000007;
int n,m,id[N][N][N],tp,f[2][M],vis[M],nw,tot,ans;
struct data{int l,x;};
vector <data> vt[N];
int getint()
{
char ch;
while(!isdigit(ch=getchar()));
int x=ch-48;
while(isdigit(ch=getchar())) x=x*10+ch-48;
return x;
}
void inc(int x,int y)
{
if(vis[x]!=nw) f[tp][x]=0,vis[x]=nw;
f[tp][x]=(f[tp][x]+y)%mod;
}
int main()
{
n=getint(),m=getint();
rep(i,1,m)
{
int l=getint(),r=getint(),x=getint();
vt[r].pb((data){l,x});
}
memset(vis,-1,sizeof(vis));
rep(i,0,n) rep(j,0,max(0,i-1)) rep(k,0,max(0,j-1)) id[i][j][k]=++tot;
f[0][id[0][0][0]]=1,vis[id[0][0][0]]=0;
rep(i,1,n)
{
tp^=1,nw=i;
rep(x,0,i-1)
rep(y,0,max(0,x-1))
rep(z,0,max(0,y-1))
if(vis[id[x][y][z]]==i-1)
{
int tmp=f[tp^1][id[x][y][z]];
inc(id[i][y][z],tmp);
inc(id[i][x][z],tmp);
inc(id[i][x][y],tmp);
}
rep(x,0,i)
rep(y,0,max(0,x-1))
rep(z,0,max(0,y-1))
{
int sz=vt[i].size();
bool jdg=0;
rep(j,0,sz-1)
{
int l=vt[i][j].l;
int t=(x>=l)+(y>=l)+(z>=l);
if(t!=vt[i][j].x) {jdg=1; break;}
}
if(jdg) vis[id[x][y][z]]=-1;
}
}
rep(i,1,tot) if(vis[i]==n) ans=(ans+f[tp][i])%mod;
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - RGB Sequence |
User |
superguymj |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1538 Byte |
Status |
AC |
Exec Time |
1461 ms |
Memory |
161536 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
7 ms |
24832 KB |
0_01.txt |
AC |
7 ms |
24832 KB |
0_02.txt |
AC |
6 ms |
22784 KB |
0_03.txt |
AC |
8 ms |
26880 KB |
1_00.txt |
AC |
1392 ms |
156416 KB |
1_01.txt |
AC |
1106 ms |
156032 KB |
1_02.txt |
AC |
1157 ms |
158464 KB |
1_03.txt |
AC |
1381 ms |
141568 KB |
1_04.txt |
AC |
1461 ms |
160512 KB |
1_05.txt |
AC |
1128 ms |
160000 KB |
1_06.txt |
AC |
1099 ms |
160512 KB |
1_07.txt |
AC |
1152 ms |
131328 KB |
1_08.txt |
AC |
1338 ms |
160128 KB |
1_09.txt |
AC |
1144 ms |
160000 KB |
1_10.txt |
AC |
1085 ms |
160000 KB |
1_11.txt |
AC |
1049 ms |
131328 KB |
1_12.txt |
AC |
1154 ms |
160000 KB |
1_13.txt |
AC |
1149 ms |
160512 KB |
1_14.txt |
AC |
1087 ms |
160000 KB |
1_15.txt |
AC |
1423 ms |
153984 KB |
1_16.txt |
AC |
1377 ms |
160256 KB |
1_17.txt |
AC |
1165 ms |
160512 KB |
1_18.txt |
AC |
1061 ms |
160000 KB |
1_19.txt |
AC |
1092 ms |
139520 KB |
1_20.txt |
AC |
1334 ms |
160128 KB |
1_21.txt |
AC |
1156 ms |
160512 KB |
1_22.txt |
AC |
1120 ms |
160128 KB |
1_23.txt |
AC |
1381 ms |
160128 KB |
1_24.txt |
AC |
1312 ms |
160128 KB |
1_25.txt |
AC |
1127 ms |
160512 KB |
1_26.txt |
AC |
958 ms |
160128 KB |
1_27.txt |
AC |
1083 ms |
131328 KB |
1_28.txt |
AC |
1404 ms |
160000 KB |
1_29.txt |
AC |
1140 ms |
160128 KB |
1_30.txt |
AC |
1062 ms |
160128 KB |
1_31.txt |
AC |
1326 ms |
160000 KB |
1_32.txt |
AC |
1294 ms |
160256 KB |
1_33.txt |
AC |
1114 ms |
160512 KB |
1_34.txt |
AC |
1072 ms |
160000 KB |
1_35.txt |
AC |
1090 ms |
160000 KB |
1_36.txt |
AC |
1091 ms |
160000 KB |
1_37.txt |
AC |
1126 ms |
156032 KB |
1_38.txt |
AC |
1177 ms |
158848 KB |
1_39.txt |
AC |
1145 ms |
141952 KB |
1_40.txt |
AC |
1405 ms |
161536 KB |
1_41.txt |
AC |
1372 ms |
160512 KB |
1_42.txt |
AC |
1378 ms |
160512 KB |