Submission #8939651


Source Code Expand

Copy
// by adiforluls
#pragma GCC optimize ("-O2")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define FAST            ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll              long long
#define ld              long double
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define mii             map<int,int>
#define vi              vector<int>
#define vll             vector<long long>
#define all(a)          (a).begin(),(a).end()
#define clz(a)          __builtin_clz(a) // count leading zeroes
#define ctz(a)          __builtin_ctz(a) // count trailing zeroes
#define popc(a)         __builtin_popcount(a) // count set bits (for ints only diff for ll)
#define lul             1000000007
#define rep(i,a,b)      for(int i=a;i<b;i++)
#define rfor(i,a,b)     for(int i=a; i>=b; i--)
#define debug(x)        cerr << #x << " = " << x << endl;
#define F               first
#define S               second
#define mod             998244353 
#define pll             pair<ll,ll>
#define endl            '\n'
#define deci(n)         cout<<fixed<<setprecision(n)
#define ordered_set     tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key(k)
// find_by_order(k)
const ld PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
#define N    100005

void solve()
{
    int n; cin>>n; 
    string s; cin>>s;
    unordered_map<char,int> ma;
    vll dist(n+1,0);
    vector<vll> dp(n+1,vll(10,0));
    vll ans(10,0);
    rep(i,1,n+1)
    {
        if(ma.count(s[i-1]))
        {
            dist[i] = dist[i-1];
            continue;
        }
        dist[i] = dist[i-1] + 1;
        ma[s[i-1]]++;
    }
    rep(i,2,n+1)
    {
        rep(j,0,10) dp[i][j] = dp[i-1][j];
        dp[i][s[i-1]-'0'] = dist[i-1];
    }
    rep(i,3,n+1)
    {
        ans[s[i-1]-'0']=0;
        rep(j,0,10)
        {
            ans[s[i-1]-'0']+=dp[i-1][j];
        }
    }
    rep(i,1,10) ans[i]+=ans[i-1];
    cout<<ans[9];
}
int main()
{   
    FAST;
   //  #ifndef ONLINE_JUDGE
     // freopen("input.txt", "r", stdin);
     // freopen("output.txt", "w", stdout);
   //  #endif
    int t; t=1;  //cin>>t;
    while(t--){
       solve();
    }
    return 0;
}

Submission Info

Submission Time
Task D - Lucky PIN
User adiforluls
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2426 Byte
Status
Exec Time 6 ms
Memory 4096 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 400 / 400 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-corner-01.txt, 01-corner-02.txt, 01-corner-03.txt, 01-corner-04.txt, 02-random-01.txt, 02-random-02.txt, 02-random-03.txt, 02-random-04.txt, 02-random-05.txt, 02-random-06.txt, 02-random-07.txt, 03-random-x-01.txt, 03-random-x-02.txt, 03-random-x-03.txt, 04-expand-01.txt, 04-expand-02.txt, 04-expand-03.txt, 04-expand-04.txt, 04-expand-05.txt, 04-expand-06.txt, 04-expand-07.txt, 04-expand-08.txt, 05-limiting-01.txt, 05-limiting-02.txt, 05-limiting-03.txt, 05-limiting-04.txt, 05-limiting-05.txt, 05-limiting-06.txt, 05-limiting-07.txt, 05-limiting-08.txt
Case Name Status Exec Time Memory
00-sample-01.txt 1 ms 256 KB
00-sample-02.txt 1 ms 256 KB
00-sample-03.txt 1 ms 256 KB
01-corner-01.txt 1 ms 256 KB
01-corner-02.txt 1 ms 256 KB
01-corner-03.txt 1 ms 256 KB
01-corner-04.txt 1 ms 256 KB
02-random-01.txt 1 ms 256 KB
02-random-02.txt 1 ms 256 KB
02-random-03.txt 1 ms 256 KB
02-random-04.txt 1 ms 256 KB
02-random-05.txt 1 ms 256 KB
02-random-06.txt 1 ms 256 KB
02-random-07.txt 6 ms 4096 KB
03-random-x-01.txt 3 ms 1536 KB
03-random-x-02.txt 4 ms 2816 KB
03-random-x-03.txt 6 ms 4096 KB
04-expand-01.txt 5 ms 3968 KB
04-expand-02.txt 5 ms 3968 KB
04-expand-03.txt 5 ms 3968 KB
04-expand-04.txt 6 ms 3968 KB
04-expand-05.txt 6 ms 3968 KB
04-expand-06.txt 6 ms 3968 KB
04-expand-07.txt 5 ms 3968 KB
04-expand-08.txt 5 ms 3968 KB
05-limiting-01.txt 6 ms 4096 KB
05-limiting-02.txt 6 ms 4096 KB
05-limiting-03.txt 6 ms 3968 KB
05-limiting-04.txt 6 ms 3968 KB
05-limiting-05.txt 6 ms 3968 KB
05-limiting-06.txt 6 ms 3968 KB
05-limiting-07.txt 6 ms 3968 KB
05-limiting-08.txt 6 ms 3968 KB