Submission #1531425
Source Code Expand
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//long long tbl[100100];
struct loc {
long long val;
int ls,idx;
};
bool operator< (const loc &a, const loc &b) {
return a.val<b.val;
}
vector<long long> cube;
vector<long long> sq;
vector<loc> work;
//vector<long long> ls[100100];
vector<int> cntt[100100];
bool find(vector<long long> &tbl,long long x) {
return (*lower_bound(tbl.begin(),tbl.end(),x))==x;
}
bool find2(vector<loc> &tbl,long long x,loc &out) {
auto tmp = lower_bound(tbl.begin(),tbl.end(),loc{x,0,0});
if (tmp->val==x) {
out=*tmp;
return true;
}
return false;
}
int mic[1010][2];
int solve(int ls,int x,int sel) {
if (x==0) return mic[x][sel]= (sel)?cntt[ls][0]:0;
if (mic[x][sel]!=-1) return mic[x][sel];
if (sel) {
return mic[x][sel]=cntt[ls][x]+solve(ls,x-1,0);
} else {
return mic[x][sel]=max(solve(ls,x-1,0),solve(ls,x-1,1));
}
}
int main () {
int n;
scanf("%d",&n);
for (long long i=1;i*i*i<=1e10;i++) {
cube.push_back(i*i*i);
}
for (long long i=1;i*i<=1e10;i++) {
sq.push_back(i*i);
}
for (long long i=2;i<1e5;i++) {
if (find(cube,i)) continue;
if (find(sq,i)) continue;
//printf("%lld\n",i);
for (long long j=i;j<=1e10;j*=j) {
if (j==0) break;
//printf("%lld\n",j);
//scanf("%d",&n);
work.push_back(loc{j,(int)i,(int)cntt[i].size()});
//ls[i].push_back(j);
cntt[i].push_back(0);
}
}
sort(work.begin(),work.end());
long long x;
int ans=0;
//int mree=0;
bool cb=false;
for (int i=0;i<n;i++) {
scanf("%lld",&x);
loc now;
if (find(cube,x)) {
//printf("a %lld\n",x);
cb=true;
} else if (find2(work,x,now)) {
cntt[now.ls][now.idx]++;
//printf("b %lld %d\n",x,now.ls);
} else if (x>1e5) {
ans++;
//mree++;
}
//else {
//printf("c %lld\n",x);
//}
}
for (int i=2;i<=1e5;i++) {
memset(mic,-1,sizeof(mic));
if (cntt[i].size()==0) continue;
int tmp = max(solve(i,cntt[i].size()-1,0),solve(i,cntt[i].size()-1,1));
ans+=tmp;
//if (i==68672) {
//printf("-- %d\n",cntt[i].size()-1);
//for (int j=0;j<(int)cntt[i].size();j++) {
//printf("%lld, %d, %d, %d\n",ls[i][j],cntt[i][j],mic[j][0],mic[j][1]);
//}
//printf("%d %d\n",i,tmp);
//}
}
printf("%d\n",ans+cb);
return 0;
}
Submission Info
Submission Time
2017-08-21 16:08:15+0900
Task
D - Anticube
User
milmillin
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2387 Byte
Status
RE
Exec Time
3644 ms
Memory
0 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:52:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:78:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1100
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt, s3.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name
Status
Exec Time
Memory
01.txt
RE
3644 ms
-1569288 KB
02.txt
RE
3066 ms
-1569284 KB
03.txt
RE
3017 ms
-1569284 KB
04.txt
RE
3117 ms
-1569264 KB
05.txt
RE
3087 ms
-1569284 KB
06.txt
RE
3030 ms
-1569284 KB
07.txt
RE
3061 ms
-1569284 KB
08.txt
RE
3043 ms
-1569284 KB
09.txt
RE
3065 ms
-1569284 KB
10.txt
RE
3052 ms
-1569284 KB
11.txt
RE
3058 ms
-1569284 KB
12.txt
RE
3075 ms
-1569284 KB
13.txt
RE
3067 ms
-1569288 KB
14.txt
RE
3019 ms
-1569284 KB
15.txt
RE
3001 ms
-1569284 KB
16.txt
RE
3103 ms
-1569284 KB
17.txt
RE
3072 ms
-1569296 KB
18.txt
RE
3019 ms
-1569284 KB
19.txt
RE
3006 ms
-1569284 KB
20.txt
RE
2994 ms
-1569284 KB
21.txt
RE
2986 ms
-1569284 KB
22.txt
RE
3027 ms
-1569284 KB
23.txt
RE
3061 ms
-1569284 KB
24.txt
RE
3092 ms
-1569284 KB
25.txt
RE
2997 ms
-1569284 KB
26.txt
RE
3052 ms
-1569284 KB
27.txt
RE
2999 ms
-1569284 KB
28.txt
RE
2979 ms
-1569284 KB
29.txt
RE
2971 ms
-1569284 KB
30.txt
RE
3079 ms
-1569284 KB
31.txt
RE
3073 ms
-1569284 KB
32.txt
RE
3017 ms
-1569284 KB
33.txt
RE
2976 ms
-1569284 KB
34.txt
RE
3049 ms
-1569284 KB
35.txt
RE
3026 ms
-1569284 KB
36.txt
RE
2970 ms
-1569284 KB
37.txt
RE
2970 ms
-1569284 KB
38.txt
RE
3052 ms
-1569284 KB
39.txt
RE
3008 ms
-1569284 KB
40.txt
RE
3078 ms
-1569284 KB
41.txt
RE
2999 ms
-1569284 KB
42.txt
RE
3078 ms
-1569284 KB
43.txt
RE
3079 ms
-1569284 KB
44.txt
RE
3059 ms
-1569284 KB
45.txt
RE
3026 ms
-1569284 KB
46.txt
RE
2982 ms
-1569284 KB
47.txt
RE
3079 ms
-1569284 KB
48.txt
RE
3078 ms
-1569284 KB
s1.txt
RE
3014 ms
-1569284 KB
s2.txt
RE
3079 ms
-1569284 KB
s3.txt
RE
3012 ms
-1569284 KB