#505040 (C++17) No.732 3PrimeCounting

• 問題: No.732 3PrimeCounting
• ユーザー: mugen_1337
• 提出日時: 2020-06-30 21:40:15
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 409 ms / 3,000 ms
• コード長: 1,220 bytes
• コンパイル時間: 3,584 ms
• コンパイル使用メモリ: 202,156 KB
• 実行使用メモリ: 6,124 KB
• 最終ジャッジ日時: 2023-10-11 12:36:51
• 合計ジャッジ時間: 11,157 ms
• ジャッジサーバーID （参考情報）: judge15 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 4,544 KB
testcase_01	AC	5 ms; 4,576 KB
testcase_02	AC	5 ms; 4,592 KB
testcase_03	AC	5 ms; 4,592 KB
testcase_04	AC	5 ms; 4,648 KB
testcase_05	AC	5 ms; 4,640 KB
testcase_06	AC	5 ms; 4,532 KB
testcase_07	AC	5 ms; 4,548 KB
testcase_08	AC	5 ms; 4,588 KB
testcase_09	AC	5 ms; 4,560 KB
testcase_10	AC	5 ms; 4,584 KB
testcase_11	AC	5 ms; 4,512 KB
testcase_12	AC	4 ms; 4,592 KB
testcase_13	AC	5 ms; 4,524 KB
testcase_14	AC	5 ms; 4,772 KB
testcase_15	AC	5 ms; 4,544 KB
testcase_16	AC	5 ms; 4,556 KB
testcase_17	AC	5 ms; 4,592 KB
testcase_18	AC	5 ms; 4,732 KB
testcase_19	AC	5 ms; 4,780 KB
testcase_20	AC	8 ms; 4,776 KB
testcase_21	AC	16 ms; 4,540 KB
testcase_22	AC	15 ms; 4,624 KB
testcase_23	AC	6 ms; 4,636 KB
testcase_24	AC	6 ms; 4,536 KB
testcase_25	AC	23 ms; 4,676 KB
testcase_26	AC	18 ms; 4,640 KB
testcase_27	AC	9 ms; 4,576 KB
testcase_28	AC	9 ms; 4,680 KB
testcase_29	AC	13 ms; 4,640 KB
testcase_30	AC	13 ms; 4,520 KB
testcase_31	AC	16 ms; 4,772 KB
testcase_32	AC	20 ms; 4,528 KB
testcase_33	AC	20 ms; 4,660 KB
testcase_34	AC	20 ms; 4,528 KB
testcase_35	AC	17 ms; 4,636 KB
testcase_36	AC	17 ms; 4,512 KB
testcase_37	AC	7 ms; 4,596 KB
testcase_38	AC	7 ms; 4,648 KB
testcase_39	AC	17 ms; 4,652 KB
testcase_40	AC	16 ms; 4,556 KB
testcase_41	AC	17 ms; 4,540 KB
testcase_42	AC	17 ms; 4,736 KB
testcase_43	AC	14 ms; 4,772 KB
testcase_44	AC	14 ms; 4,592 KB
testcase_45	AC	10 ms; 4,524 KB
testcase_46	AC	10 ms; 4,592 KB
testcase_47	AC	12 ms; 4,516 KB
testcase_48	AC	25 ms; 4,552 KB
testcase_49	AC	24 ms; 4,680 KB
testcase_50	AC	15 ms; 4,536 KB
testcase_51	AC	16 ms; 4,644 KB
testcase_52	AC	10 ms; 4,508 KB
testcase_53	AC	42 ms; 4,640 KB
testcase_54	AC	194 ms; 5,372 KB
testcase_55	AC	193 ms; 5,348 KB
testcase_56	AC	193 ms; 5,372 KB
testcase_57	AC	76 ms; 4,904 KB
testcase_58	AC	76 ms; 4,788 KB
testcase_59	AC	45 ms; 4,688 KB
testcase_60	AC	96 ms; 4,892 KB
testcase_61	AC	96 ms; 4,964 KB
testcase_62	AC	230 ms; 5,552 KB
testcase_63	AC	138 ms; 5,152 KB
testcase_64	AC	111 ms; 5,020 KB
testcase_65	AC	111 ms; 4,956 KB
testcase_66	AC	6 ms; 4,588 KB
testcase_67	AC	5 ms; 4,592 KB
testcase_68	AC	209 ms; 5,420 KB
testcase_69	AC	209 ms; 5,464 KB
testcase_70	AC	194 ms; 5,336 KB
testcase_71	AC	195 ms; 5,464 KB
testcase_72	AC	132 ms; 5,120 KB
testcase_73	AC	318 ms; 5,948 KB
testcase_74	AC	316 ms; 5,956 KB
testcase_75	AC	23 ms; 4,612 KB
testcase_76	AC	206 ms; 5,512 KB
testcase_77	AC	80 ms; 4,872 KB
testcase_78	AC	266 ms; 5,748 KB
testcase_79	AC	211 ms; 5,464 KB
testcase_80	AC	243 ms; 5,696 KB
testcase_81	AC	197 ms; 5,420 KB
testcase_82	AC	9 ms; 4,640 KB
testcase_83	AC	78 ms; 4,916 KB
testcase_84	AC	84 ms; 4,956 KB
testcase_85	AC	177 ms; 5,344 KB
testcase_86	AC	252 ms; 5,604 KB
testcase_87	AC	409 ms; 6,092 KB
testcase_88	AC	401 ms; 6,124 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

vector<int> sieve(int n){
    vector<int> ret(n+1,true);
    ret[0]=false;
    if(n>0) ret[1]=false;
    for(int i=2;i*i<=n;i++){
        if(!ret[i]) continue;
        for(int j=i*2;j<=n;j+=i) ret[j]=false;
    }
    return ret;
}

ll cnt[300000],ans;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    auto isp=sieve(300000);
    vector<int> ps;
    rep(i,300000)if(isp[i])ps.push_back(i);
    


    int n;cin>>n;
    for(int i=0;ps[i]<=n;i++){
        int c=ps[i];

        rep(j,ps.size()){
            int sum=ps[j];
            if(sum-c>=0) ans+=cnt[sum-c];
        }

        rep(j,i) cnt[c+ps[j]]++;
    }
    cout<<ans<<endl;
    return 0;
}