akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main p = new Main();
	}
	
	public Main(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] data = new int[n][10];
		for(int i=0;i<n;i++){
			for(int j=0;j<10;j++){
				data[i][j] = sc.nextInt();
			}
		}
		
		solve(data);
	}
		
	private void solve(int[][] data){
		for(int i=0;i<data.length;i++){
			if(rec(data[i], 1, data[i][0], -1)){
				System.out.println("YES");
			}else{
				System.out.println("NO");
			}
		}
	}
	
	private boolean rec(int[] row, int cur, int left, int right){
		if(cur>=10)
			return true;
		
		boolean res = false;
		
		if(row[cur]>left)
			res |= rec(row, cur+1, row[cur], right);
		
		if(!res && row[cur]>right)
			res |= rec(row, cur+1, left, row[cur]);
		
		return res;
		
	}
}

Measured memory_bytes: 18400
#include <iostream>
#include <vector>
using namespace std;

vector<int> graph[100];
int start[100],endt[100];
int cnt;

void dfs(int num){
	start[num] = ++cnt;
	for(int i = 0;i < graph[num].size();i++){
		if(graph[num][i] != num && !start[graph[num][i]] && !endt[graph[num][i]]) dfs(graph[num][i]);
	}
	endt[num] = ++cnt;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		int now,m;
		cin >> now >> m;
		for(int j = 0;j < m;j++){
			int t;
			cin >> t;
			graph[now - 1].push_back(t - 1);
		}
	}
	dfs(0);
	for(int i = 0;i < n;i++){
		if(!endt[i]) dfs(i);
	}
	for(int i = 0;i < n;i++){
		cout << i + 1 << " " << start[i] << " " << endt[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3144
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

    int N;
    cin >> N;

    bool zero = false;
    vector<LL> A(N);
    rep(i, N) {
        cin >> A[i];
        if (!A[i]) zero = true;
    }

    LL ans = 0;
    if (!zero) {
        ans = 1;
        for (int i = 0; i < N && 0 < ans; ++i) {
            if (1000000000000000000LL / ans < A[i]) {
                ans = -1;
            } else {
                ans *= A[i];
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin>>N;
  vector<int> p(N);
  for(int i=0;i<N;i++) cin>>p[i];
  int q[N];
  for(int i=0;i<N;i++) q[i]=p[i];
  sort(p.begin(),p.end());
  int reg=0;
  for(int i=0;i<N;i++){
    if(p[i]!=q[i]) reg++;
  }
  if(reg==2||reg==0) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
};
int a[4][4];
map<int,node>mp;
int n;
bool b[110],bol[4][4];
int main()
{
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			cin>>a[i][j];
			mp[a[i][j]].x=i;
			mp[a[i][j]].y=j;
			b[a[i][j]]=1;
		}
	cin>>n;
	for(int i=1,c;i<=n;i++)
	{
		cin>>c;
		if(b[c])
			bol[mp[c].x][mp[c].y]=1;
	}
	if(bol[1][1]&&bol[1][2]&&bol[1][3])puts("Yes");
	else if(bol[2][1]&&bol[2][2]&&bol[2][3])puts("Yes");
	else if(bol[3][1]&&bol[3][2]&&bol[3][3])puts("Yes");
	else if(bol[1][1]&&bol[2][1]&&bol[3][1])puts("Yes");
	else if(bol[1][2]&&bol[2][2]&&bol[3][2])puts("Yes");
	else if(bol[1][3]&&bol[2][3]&&bol[3][3])puts("Yes");
	else if(bol[1][1]&&bol[2][2]&&bol[3][3])puts("Yes");
	else if(bol[1][3]&&bol[2][2]&&bol[3][1])puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int N,K,r;
    r=0;
    cin>>N>>K;
    vector<int> h(N);
    for(int i=0;i<N;i++){
        cin>>h.at(i);
        if(h.at(i)>=K){
            r++;
        }
    }
    cout<<r<<endl;

}

Measured memory_bytes: 640
N,K=map(int,input().split())
h=[0]*N
for x in range(N):
  h[x]=int(input())
h.sort()
c=1000000000
for i in range(N-K+1):
  if h[i+K-1]-h[i]<c:
    c=h[i+K-1]-h[i]
print(c)

Measured memory_bytes: 13304
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    int n;
    string str, com;
    map<string, bool> dict;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> com >> str;
        if (com[0] == 'i') {
            dict[str] = true;
        } else {
            if (dict[str]) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        }
    }
}



Measured memory_bytes: 52588
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1010;

int x, x2, x3, x4;
int y, y2, y3, y4;

int main()
{
    scanf("%d%d%d%d", &x, &y, &x2, &y2);

    x3 = x2 - (y2 - y);
    y3 = y2 + (x2 - x);
    x4 = x - (y2 - y);
    y4 = y + (x2 - x);

    printf("%d %d %d %d\n", x3, y3, x4, y4);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main()
{
       int d,n;
       long long x=1;
       cin>>d>>n;

       for(int i=0;i<d;i++)
       x*=100;
       if(n!=100)
       cout<<n*x;
       else cout<<x*(n+1);

    return 0;
   }

Measured memory_bytes: 3600
// in the name of Allah ;
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e2 + 10 ;
int t[maxn] , tt[maxn] ,  p[maxn] , x[maxn] ,n , m ;
void input()
{
	cin >> n ;
	for ( int i = 0 ; i < n ; i++ ) 
		cin >> t[i] ;
	cin >> m ;
	for ( int i = 0 ; i < m ; i++ ) 
		cin >> p[i] >> x[i]  ;
}
int main ()
{
	input() ;
	for ( int i = 0 ; i < m ; i++ )
	{
		int ans = 0 ;
		p[i]-- ;
		for ( int j = 0 ; j < n ; j++ )
			if ( p[i] != j ) 
				ans += t[j] ; 
			else
				ans += x[i]  ;
		cout << ans << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long

int nCm(int n,int m){
	m=min(m,n-m);
	if(	m==0)return 1;
	else return nCm(n-1,m-1)*n/m;
}

signed main(){
	int n,a,b;cin>>n>>a>>b;
	vector<int> v(n);
	for(auto&& w:v)cin>>w;

	sort(v.begin(),v.end(),greater<int>());
	int a0=v[a-1];  
  
	int sm=accumulate(v.begin(),v.begin()+a,0ll);
	double avg=(double)sm/a;

	
		

	int x=count(v.begin(),v.end(),a0);
	int y=count(v.begin(),v.begin()+a,a0);
  	cerr<<x<<" "<<y<<" "<<nCm(x,y)<<endl;
	int cnt=0;int b0=min(b,y-x+a);
	if(v[0]>a0){cnt=nCm(x,y);}
	else {
		 for(int i=0;i+a<=b && y+i<=x;i++){
		cnt+=nCm(x,(y+i));}
	}  

	cout<<setprecision(10);
	cout<<avg<<endl;
	cout<<cnt<<endl;	
}

Measured memory_bytes: 764
#include<stdio.h>
#include<string.h>
char plus[200][20];
char neg[200][20];
int main(void){
    int blue,red,i,j,ans=0,temp;
    for(i=0;i<200;i++){
        for(j=0;j<20;j++){
            plus[i][j]=0;
            neg[i][j]=0;
        }
    }
    scanf("%d",&blue);
    for(i=0;i<blue;i++){
        scanf("%s",plus[i]);
    }
    scanf("%d",&red);
    for(i=0;i<red;i++){
        scanf("%s",neg[i]);
    }
    for(i=0;i<blue;i++){
        temp=0;
        for(j=0;j<blue;j++){
            if(strcmp(plus[i],plus[j])==0){
                temp++;
            }
        }
        for(j=0;j<red;j++){
            if(strcmp(plus[i],neg[j])==0){
                temp--;
            }
        }
              if(temp>ans){
            ans=temp;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll f[2][10 * 14 + 2][20000][3];
ll n;
vector <ll> Hash;
int go[20010][10];
int number[15];
void init(){
    set <ll> s;
    s.insert(1);
    for (int i = 1; i <= 14; ++ i){
        set <ll> st;

        for (ll x : s){
            for (int j = 1; j <= 10; ++ j){
                st.insert(x * j);
            }
        }
        for (ll x : st){
            s.insert(x);
        }
    }

    for (ll x : s){
        Hash.push_back(x);
    }
}
int getID(ll x){
    int pos = lower_bound(Hash.begin(), Hash.end(), x) - Hash.begin();
    return pos;
}
char ch[20];
int main(){
    init();
    scanf("%s", ch);
    int len = strlen(ch);

    int ySum = 0;

    for (int i = len - 1; i >= 0; -- i){
        number[len - i] = ch[i] - '0';
        ySum += ch[i] - '0';
    }
    n = 1;
    for (int i = 0; i < len; ++ i){
        n = n * (ch[i] - '0' + 1);
    }

    int num = Hash.size();
    int yID = getID(n);

    for (int i = 0; i < num; ++ i){
        for (int j = 1; j <= 10; ++ j){
            int id = getID(Hash[i] * j);
            go[i][j - 1] = id;
        }
    }
    //printf("%d %lld\n", ySum, n);
    for (int j = 0; j <= 9 * 14; ++ j){
        for (int k = 0; k < num; ++ k){
            for (int l = 0; l <= 2; ++ l){
                if (j < ySum){
                    f[0][j][k][l] = 1;
                }
                if (j == ySum && k < yID){
                    f[0][j][k][l] = 1;
                }
                if (j == ySum && k == yID && l == 0){
                    f[0][j][k][l] = 1;
                }
            }
        }
    }
    //for (int i = 1; i <= len; ++ i) printf("%d ", number[i]); puts("");
    ll pow10[15];
    pow10[0] = 1;
    for (int i = 1; i <= 14; ++ i) pow10[i] = pow10[i - 1] * 10;
    //puts("da");
    int now = 0, nxt = 1;
    for (int i = 1; i <= len; ++ i){
        //printf("%d\n", i);
        memset(f[nxt], 0, sizeof f[nxt]);
        for (int j = 0; j <= 9 * (len - i); ++ j){
            for (int k = 0; k < num; ++ k){

                for (int l = 0; l <= 2; ++ l){
                    int maxn = number[i];
                    for (int m = 0; m <= 9; ++ m){
                        int status = go[k][m];
                        //if (m < 2 && i == 2 && j == 0 && k == 0 && l == 1) printf("%d %d %d\n", j + m, maxn, l & (m == maxn));
                        if (l == 1){
                            int flag = 1;
                            if (m > maxn) flag = 2;
                            else if (m < maxn) flag = 0;
                            f[nxt][j][k][l] += f[now][j + m][status][flag];
                        } else
                            f[nxt][j][k][l] += f[now][j + m][status][l];
                    }
                }
            }
        }
        swap(now, nxt);
    }
    //printf("%lld\n", f[2][0][0][1]);
    //printf("%lld\n", f[0][2][2][0]);
    //printf("%lld\n", f[0][1][1][0]);
    //printf("%lld\n", f[0][0][0][0]);
    printf("%lld\n", f[now][0][0][1]);
}

Measured memory_bytes: 138880
#include <bits/stdc++.h>

#define rev(v) reverse(v.begin(), v.end());
#define mx(v) max_element(v.begin(), v.end());
#define mn(v) min_element(v.begin(), v.end()); 
#define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));

//ffs = lsb, clz = l0's, ctz = r0's, popcount = 1's 
 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
using namespace std;
 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
    fastio();
    int a,x; cin >> a >> x;
    if(a < x){
        cout << '0';
    }else{
        cout << "10\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(void) {
    int x;
    cin >> x;
    puts((1200>x)?"ABC":"ARC");
    return 0;
}


Measured memory_bytes: 256
/*
 * atcoder/abc132/e.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

#include <queue>
const int MAX = 100001;
const int INF = 10000000;
int N, M, S, T;
vector<int> G[MAX];
int dist[MAX][3];
int bfs() {
  queue<pair<int, int> > Q;
  Q.push({S, 0});
  dist[S][0] = 0;

  while (Q.size()) {
    auto p = Q.front(); Q.pop();
    int u = p.first;
    int d = p.second;
    d++;
    for (auto&& v: G[u]) {
      if (dist[v][d%3] < INF) continue;
      dist[v][d%3] = d;
      Q.push({ v, d });
      if (v == T and d%3==0) {
        return d/3;
      }
    }
  }

  return -1;
}

void solve() {
  cin >> N >> M;
  int a, b;
  loop(m,0,M) {
    cin >> a >> b;
    a--;b--;
    G[a].push_back(b);
  }
  cin >> S >> T;
  S--;T--;
  loop(i,0,N+1) {
    loop(j,0,3) {
      dist[i][j] = INF;
    }
  }

  cout << bfs() << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 6912
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        Integer n = Integer.parseInt(scanner.next());
        Integer k = Integer.parseInt(scanner.next());
        Integer q = Integer.parseInt(scanner.next());

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        int[] a = new int[q];

        for(int i = 0; i < q; i++) {
            a[i] = Integer.parseInt(scanner.next());
        }

        int[] d = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = k;
        }

        for(int i= 0; i < a.length; i++) {
            d[a[i] -1] +=  1;
        }


        for(int i= 0; i < d.length; i++) {
            if(d[i] - q  > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }

    }
}


Measured memory_bytes: 49136
#include <bits/stdc++.h>
using namespace std;

// #define double long double

const double EPS = 1e-9;

struct P {
  double x, y, z;
  P() {}
  P(double x, double y, double z): x(x), y(y), z(z) {}
};

int N, M;
vector<P> stars, scopes;
vector<double> angs;

double dist(P a, P b) {
  return sqrt(pow(a.x-b.x, 2)+pow(a.y-b.y, 2)+pow(a.z-b.z, 2));
}

bool contain(int a, int b) {
  double l = 0, r = 1000000;
  int cnt = 100;
  P A = stars[a];
  while ( cnt-- ) {
    double mid = (l+r)/2;
    P B = scopes[b];
    B.x *= mid; B.y *= mid; B.z *= mid;
    double dist1 = dist(A, B);
    B = scopes[b];
    B.x *= (mid+EPS); B.y *= (mid+EPS); B.z *= (mid+EPS);
    double dist2 = dist(A, B);
    if ( dist1 > dist2 ) l = mid;
    else r = mid;    
  }

  P B = scopes[b];
  B.x *= l; B.y *= l; B.z *= l;
  double dist1 = dist(P(0, 0, 0), B);
  double dist2 = dist(A, B);
  if ( dist2 < tan(angs[b])*dist1 ) return true;
  else return false;
}

int main() {
  while ( cin >> N, N ) {
    stars.resize(N);
    for ( int i = 0; i < N; i++ ) {
      cin >> stars[i].x >> stars[i].y >> stars[i].z;
    }
    
    cin >> M;
    scopes.resize(M);
    angs.resize(M);
    for ( int i = 0; i < M; i++ ) {
      cin >> scopes[i].x >> scopes[i].y >> scopes[i].z;
      cin >> angs[i];    
    }

    int ans = 0;
    for ( int i = 0; i < N; i++ ) {
      for ( int j = 0; j < M; j++ ) {
	if ( contain(i, j) ) {
	  ans++;
	  break;
	}
      }
    }

    cout << ans << endl;
  }  
  return 0;
}



Measured memory_bytes: 3480
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;
int n,a[maxn],ans,S[maxn * 10],top,num[maxn * 10];

bool check(int limit)
{
    memset(S,0,sizeof(S));
    memset(num,0,sizeof(num));
    top = 0;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > a[i - 1])
            continue;
        int x = a[i];
        while (top && S[top] > x)
            top--;
        while (top && S[top] == x && num[top] == limit)
        {
            top--;
            x--;
        }
        if (!x)
            return false;
        if (S[top] < x)
        {
            S[++top] = x;
            num[top] = 2;
            if (limit == 1)
                return false;
        }
        else
        {
            num[top]++;
            if (num[top] > limit)
                return false;
        }

    }
    return true;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    int l = 1,r = n;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 16640
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict

def main():
    N = I()
    ans = 0
    for i in range(1, N):
        x, y = divmod(N, i)
        ans += x
        if y == 0:
            ans -= 1


    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 68588
#include <bits/stdc++.h>

#define LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int N = 200001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct edge {
	int x, y, next;
} e[2 * N]; int len, last[N];
unordered_map<int, int> mp[N];
int ans[N], f[N];

void ins(int x, int y) {
	e[++len].x = x, e[len].y = y;
	e[len].next = last[x], last[x] = len;
}

int dfs1(int x, int fa, int mx) {
	if(mp[x].count(mx)) return mp[x][mx];
	int sum = 0;
	for(int k = last[x]; k; k = e[k].next) if(e[k].y != fa){
		int y = e[k].y;
		if(y > mx) continue;
		else sum += dfs1(y, x, mx) + 1;
	} return mp[x][mx] = sum;
}

void dfs2(int x, int fa) {
	f[x] = _max(f[fa], fa);
	if(x == 1) ans[x] = 0;
	else {
		if(x > f[fa]) ans[x] = ans[fa] + dfs1(x, fa, f[x]) + 1;
		else ans[x] = ans[fa] + dfs1(x, fa, f[x]) - dfs1(x, fa, f[fa]);
	} for(int k = last[x]; k; k = e[k].next) if(e[k].y != fa) dfs2(e[k].y, x);
}

int main() {
	int n = read();
	for(int i = 1; i < n; i++) {
		int x = read(), y = read();
		ins(x, y), ins(y, x);
	} dfs2(1, 0);
	for(int i = 2; i <= n; i++) put(ans[i]), putchar(' ');
	return 0;
}


Measured memory_bytes: 44544
n, t, s = gets.split.map(&:to_i)
arr = n.times.map{ gets.split.map(&:to_i) }
dp = [0]*(t+1)
n.times do |i|
  a, b = arr[i]
  t.downto(b) do |j|
    dp[j] = [dp[j], dp[j - b] + a].max if !(j - b < s && s < j)
  end
end
p dp.max

Measured memory_bytes: 8836
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
typedef pair<int, int> pint;
struct town{
    int x, y;
    map<string, int> shop;
    town() {
        x = y = -1;
        shop.clear();
    }
    town(int x, int y) : x(x), y(y){ shop.clear();}
};
int N, M, W, T;
map<string, pint> products;
vector<town> towns;
int dp1[1 << 7][7];//dp[S][i] := ??????s???????????£???i???????????´??????????????????
int dist[1 << 7];
void salesman(){
    rep(i, 1 << N) rep(j, N) dp1[i][j] = INF;
    rep(i, 1 << N) dist[i] = INF;
    rep(i, N)
      dp1[1 << i][i] = abs(towns[i].x) + abs(towns[i].y);
    rep(s, 1 << N)
      rep(i, N) if(1 & (s >> i))
        rep(j, N) if(!(s >> j & 1))
          dp1[s | (1 << j)][j] = min(dp1[s | (1 << j)][j], dp1[s][i] + abs(towns[i].x - towns[j].x) + abs(towns[i].y - towns[j].y));
    rep(s, 1 << N)
      rep(i, N) if((s >> i) & 1)
        dist[s] = min(dist[s], dp1[s][i] + abs(towns[i].x) + abs(towns[i].y));
}

ll nap[1 << 7];
ll zack[10001];
void nap_zack(int s){
    memset(zack, 0, sizeof(zack));
    rep(i, N){
        if(!((s >> i) & 1)) continue;
        for(auto pro : towns[i].shop){
            pint temp = products[pro.first];
            int val = temp.second - pro.second, wei = temp.first;
            for(int j = wei; j <= W; j++)
              zack[j] = max(zack[j], zack[j - wei] + val);
        }
    }
    nap[s] = zack[W];
    return;
}
ll dp2[10001];
ll solve(){
    memset(dp2, 0, sizeof(dp2));
    rep(i, T + 1)
      rep(s, 1 << N)
        if(i >= dist[s])
          dp2[i] = max(dp2[i], dp2[i - dist[s]] + nap[s]);
    return dp2[T];
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> W >> T;
    int pn = 0;//????????????
    rep(i, M){
        string a;
        int b, c;
        cin >> a >> b >> c;
        products[a] = pint(b, c);
    }
    rep(i, N){
        int pnum, x, y;
        cin >> pnum >> x >> y;
        town temp(x, y);
        rep(j, pnum){
            string a;
            int b;
            cin >> a >> b;
            temp.shop[a] = b;
        }
        towns.push_back(temp);
    }
    salesman();
    rep(s, 1 << N) nap_zack(s);
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 3376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(ll i=0;i<x;i++)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pll = pair<ll,ll>; //(money,time)
using Edge = pair<int, pll>;
using Graph = vector<vector<Edge>>;


int N,M;
ll S;
Graph G;
vector<ll>C,D;

const ll INF = 1LL<<60;
const int MAX = 2500;


void solve(){
  if(S>=MAX) S = MAX;
  vector<vector<ll>> dp(N,vector<ll>(MAX+1,INF));
  priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>>que;
  dp[0][S] = 0;

  que.push(make_pair(0,pll(0,S)));

  while(!que.empty()){
    auto p=que.top();que.pop();

    ll time = p.first;
    int v = p.second.first;
    ll s = p.second.second;
    if(time > dp[v][s]) continue;


    // 補充
    if(s+C[v] <= MAX){
      ll ns = s+C[v];
      ll ntime = time + D[v];
      if(chmin(dp[v][ns], ntime)){
        // dp[v][ns] = ntime;
        que.push(make_pair(ntime,pll(v,ns)));
      }
    }

    for(auto e:G[v]){
      if(s<e.second.first) continue;
      int nv = e.first;
      ll ns = s - e.second.first;
      ll ntime = time + e.second.second;
      if(chmin(dp[nv][ns], ntime)){
        que.push(make_pair(ntime,pll(nv,ns)));
      }
    }
  }

  for(int v =1; v < N; v++){
    ll res = INF;
    for(int s = 0; s<=MAX; s++) chmin(res, dp[v][s]);
    cout<<res<<endl;
  }
}



int main(){
  cin >> N >> M >> S;
  G.assign(N,vector<Edge>());
  rep(i,M){
    ll u,v,a,b;
    cin>>u>>v>>a>>b;
    --u,--v;
    G[u].push_back(Edge(v,pll(a,b)));
    G[v].push_back(Edge(u,pll(a,b)));
  }
  C.resize(N); D.resize(N);
  rep(i,N) cin>>C[i]>>D[i];

  solve();
}


Measured memory_bytes: 7388
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S1 = sc.next();
        String S2 = sc.next();
        final int Mod = 1000000007; // about 1e9
        int left=0;
        long cur = 3;
        if(S1.charAt(0)!=S2.charAt(0)){
            left=1;
            cur = 6;
        }
        int right = left+1;
        while(right<N){
            if(S1.charAt(right)!=S2.charAt(right)) right++;
            if(right==left+1){
                if(S1.charAt(left)!=S2.charAt(left)) cur = cur;
                else{
                    cur = (2*cur)%Mod;
                }
            }
            else{
                if(S1.charAt(left)!=S2.charAt(left)) cur = (3*cur)%Mod;
                else cur = (2*cur)%Mod;
            }
            left = right;
            right++;
        }
        System.out.println(cur);
    }
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int i,win  = 0,lose = 0;
	char s[17];
	scanf("%s",s);
	for (i = 0; i < strlen(s); ++i)
	{
		if(s[i] == 'o')	++win;
		else ++lose;
	}
	if(win + (15 - i) >= 8)	puts("YES");
	else puts("NO");
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        String op = input.next();
        int b = input.nextInt();
        
        while (!op.equals("?")) {
            if (op.equals("+")) {
                System.out.println(a + b);
            }
            else if (op.equals("-")) {
                System.out.println(a - b);
            }
            else if (op.equals("*")) {
                System.out.println(a * b);
            }
            else if (op.equals("/")) {
                System.out.println(a / b);
            }
            else {
                break;
            }
            
            a = input.nextInt();
            op = input.next();
            b = input.nextInt();
            
        }
    }
}


Measured memory_bytes: 26252
n, k = gets.chomp.split(" ").map(&:to_i)
modZero = 0
modHarf = 0
1.upto(n) do |i|
    modZero += 1 if i % k == 0
    modHarf += 1 if k.even? && i % k == k/2
end

puts modZero**3 + modHarf**3

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;
typedef unsigned u32;
typedef unsigned long long u64;
const int N=1e5;
const u32 P=1e9+7;
int n, m, x[N], y[N];
u32 bit[N+2];
std::vector<std::pair<int, int>> e;
u32 &inc(u32 &a, u32 b) {return (a+=b)<P?a:(a-=P);}
u32 &dec(u32 &a, u32 b) {return (a-=b)&0x80000000?(a+=P):a;}
u32 sum(u32 a, u32 b) {return inc(a, b);}
u32 dif(u32 a, u32 b) {return dec(a, b);}
u32 sum(int x) {
	u32 res=0;
	for(++x; x; x&=x-1) inc(res, bit[x]);
	return res;
}
void mdf(int x, u32 y) {
	for(++x; x<=m+1; x+=x&-x) inc(bit[x], y);
}
int main() {
	n=rd(), m=rd();
	std::generate(x, x+n, rd);
	std::generate(y, y+m, rd);
	for(int i=0, j=0; i<n&&x[i]<y[m-1]; ++i) {
		while(y[j]<x[i]) ++j;
		if(j!=0&&x[i]!=y[j]) e.emplace_back(x[i]-y[j-1], y[j]-x[i]);
	}
	n=e.size();
	for(int i=0; i<n; ++i) std::tie(x[i], y[i])=e[i];
	std::sort(x, x+n), m=std::unique(x, x+n)-x;
	for(int i=0; i<n; ++i) e[i].first=std::lower_bound(x, x+m, e[i].first)-x+1;
	std::sort(y, y+n), m=std::unique(y, y+n)-y;
	for(int i=0; i<n; ++i) e[i].second=-(std::lower_bound(y, y+m, e[i].second)-y+1);
	std::sort(e.begin(), e.end());
	e.resize(std::unique(e.begin(), e.end())-e.begin());
	n=e.size();
	mdf(0, 1);
	for(auto p: e) {
		int y=-p.second;
		mdf(y, sum(y-1));
	}
	printf("%u\n", sum(m));
	return 0;
}


Measured memory_bytes: 2292
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,a[1010];
int main()
{
	cin>>n>>m;
	long long s=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	long long ans=0;
	for(int i=0;i<n;i++)
		if(double(1)/double(4*m)<=double(a[i])/double(s))
			ans++;
	//cout<<s/(4*m)<<ans<<"!!"<<endl;		
	if(m<=ans)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;		
} 

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include <utility>
#include<map>
#include<set>
#include<iterator>
#include<stack>
#include<bitset>
#include<queue>
#include<deque>
#define all(v) ((v).begin()) , ((v).end())
#define sz(v) ((int)((v).size()))
using namespace std;
set<int> st;
set<int> ::iterator it;
map<char, int> mp;
map<char, int> ::iterator itr;
/*bool co(const pair<long long, long long>&c, const pair<long long, long long>&d)
{
return c.second > d.second;
} */

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	int n;
	double av , l, a, b;
	cin >> a >> b;
	av = (a + b) / 2;
	n = (int)(av);
	l = n + 0.5;
	if (av >= l)
		cout << n + 1 << endl;
	else cout << n << endl;

}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
void program(); int main() {cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); program();}
#define int long long
#define endl "\n"
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>

#define INF numeric_limits<int>::max()
#define N 407
int a[N], ps[N], dp[N][N];
int n;

int f(int l, int r){
    if(l==r) return 0;
    if(dp[l][r] != -1) return dp[l][r];
    int opt = INF;

    int rs = 0;
    for(int i=l;i<r;i++){
        rs += a[i];
        opt = min(opt, ps[r]-ps[l-1] + f(l,i) + f(i+1,r));
    }
    return dp[l][r] = opt;
}

void program(){
    cin>>n;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) dp[i][j] = -1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) ps[i] = a[i] + ps[i-1];
    cout<<f(1,n)<<endl;
}

/*
WA:
-bounds on loops
-truncating
-intialization
-0 vs 1 indexing

TLE:
-might need unordered_set/map
-infinite while loop

Stuck:
-different perspective?
-bruteforce?
-greedy?
-reduce dimensionality with problem contraints?
*/


Measured memory_bytes: 1536
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

lint lcm(lint a, lint b) {
    return (a / gcd(a, b)) * b;
}

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint w, h, x, y;
    cin >> w >> h >> x >> y;
    double ans = (w * h) / 2.0;
    int ans2;
    if(2 * x == w && 2 * y == h){
        ans2 = 1;
    }
    else {
        ans2 = 0;
    }
    cout << ans << " " << ans2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define NL endl
#define pi 2.0*acos(0.0)
#define INTM 1e18
#define mod 1e9+7
#define FOR(i,j,n)    for(ull i=j;i<n;i++)
#define RFOR(i,j,n)    for(ll i=j;i>=n;i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;

int main(){
    fastIO;
    ll n,sum = 0,k;
    cin>>n>>k;
    ll arr[n];
    FOR(i,0,n) cin>>arr[i];
    sort(arr,arr+n,greater<ll>());
    ll ans = 0;
    FOR(i,0,n){
        if(k <= 0) ans += arr[i];
        else k--;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define MP make_pair
#define PB push_back
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int INF = 1e9 + 7;
const int maxn = 2005;

int n;
int a[maxn], vis[maxn];
vector<int> ans;
vector<int> g[maxn], tr[maxn];
priority_queue<pii> que;

inline void dfs(int u){
	vis[u] = true;
	FOR(i, 0, g[u].size()){
		int v = g[u][i];
		if(!vis[v]){
			dfs(v);
			tr[u].PB(v);
		}
	}
	return;
}

int main(){
	scanf("%d", &n);
	FOR(i, 0, n)
		scanf("%d", a + i);
	sort(a, a + n);
	FOR(i, 0, n) FOR(j, 0, n) if(i != j && __gcd(a[i], a[j]) != 1)
		g[i].PB(j);

	FOR(i, 0, n) if(!vis[i])
		dfs(i), que.PH(MP(a[i], i));
	while(!que.empty()){
		int u = que.top().snd;
		que.pop();
		ans.PB(a[u]);
		FOR(i, 0, tr[u].size())
			que.PH(MP(a[tr[u][i]], tr[u][i]));
	}
	
	FOR(i, 0, n)
		printf("%d ", ans[i]);
	puts("");
	return 0;
}


Measured memory_bytes: 19560
// Problem : 
// 			A - Rainy Season
// 			Editorial
// 		
// Contest : AtCoder - AtCoder Beginner Contest 175
// URL : https://atcoder.jp/contests/abc175/tasks/abc175_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(i,n)         for(int i=0;i<n;i++)
#define Fo(i,k,n)       for(int i=k;i<n;i++) 
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define vec(x)          vector<x>
#define matrix(x)       vector<vector<x>>
#define sz(x)           (int)x.size()
#define mem(a,b)        memset(a, b, sizeof a)
#define vii             vector<pair<int,int>>
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        (a*(b/gcd(a,b)))
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define MOD             998244353
#define deb(x)          cerr <<#x<<" = "<<x<<"\n"
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(v)          v.begin(),v.end()
#define rep(i,a,b)      for (int i = a; i<b; ++i)
#define len(s)          s.length()
#define watch(x)        cout << #x << " = " << x << endl
#define trace(x)        cerr << #x << " = " << x << endl
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int power(int a,int b,int m=mod)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}

void babuBhaiya()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

const int N = 1e5+1;
const double pi = acos(-1);

void solve(){
    
	string s; cin>>s;
	int cnt = 0;
	for(char c : s) if(c=='R') cnt++;
	if(cnt==0 or cnt ==1) cout<<cnt;
	else if(cnt == 2){
		if(s[0]=='R' and s[2]=='R') cout<<"1";
		else cout<<cnt;
	}
	else cout<<3;
	
}

 
int32_t main()
{
    babuBhaiya();

    int t;

    t = 1;
    //cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 3624
#include<iostream>

using namespace std;

int main()
{
	int x, y;
	cin >> x >> y;
	int x1, y1;
	if ((x == 4) | (x == 6) | (x == 9) | (x == 11)) x1 = 1;
	else if (x == 2) x1 = 2;
	else x1 = 3;
	if ((y == 4) | (y == 6) | (y == 9) | (y == 11)) y1 = 1;
	else if (y == 2) y1 = 2;
	else y1 = 3;
	if (x1 == y1) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();

            System.out.println(s.charAt(0) == s.charAt(2) ? "Yes": "No");
        }
    }
}


Measured memory_bytes: 21972
import math

n,m = map(int, input().split())
k = int(math.sqrt(m))
a = []
b = []
ans = 0
for i in range(1,k+10):
    if m%i==0:
        a.append(m//i)
        b.append(i)
    else:
        continue
for i in a:
    if m//i>=n:
        ans = i
        break
for i in reversed(b):
    if m//i>=n:
        ans = max(ans,i)
        break
    else:
        continue
print(ans)

Measured memory_bytes: 3064
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
#define  aryout(ary) rep(i, ary.size()) cout << ary[i] << (i < ary.size() - 1 ? " " : "\n");
#define  arysort(v) sort(v.begin(), v.end())
#define  aryreverse(v) reverse(v.begin(),v.end())
#define  arysum(v) accumulate(v.begin(), v.end(), 0)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

long long int knapsack(int n, int w, vector<pair<int, int>> trs) {

  int varmax = n+1;
  int hormax = n*1e3+1;

  vector<vector<lli>> dp(varmax, vector<lli>(hormax, n*1e9+10));

  repx (var, 1, varmax) {
    repx (hor, 1, hormax) {

      if (trs[var-1].second > hor) {
        dp[var][hor] = dp[var-1][hor];

      } else if (trs[var-1].second == hor) {
        dp[var][hor] = min(dp[var-1][hor], (lli)trs[var-1].first);

      } else {
        dp[var][hor] = min(dp[var-1][hor - (trs[var-1].second)] + (lli)trs[var-1].first, dp[var-1][hor]);
      }
    }
  }

  //rep (i, varmax) rep (j, hormax) cout << "[" << i << "][" << j << "]:" << dp[i][j] << (j == hormax ? "\n" : " ");

  lli tmpw = (lli)w;
  for (int i = hormax-1; i >= 0; i--)
    if (dp[varmax-1][i] <= tmpw) return i;

  return 0;
}

int main() {

  int n, w;
  cin >> n >> w;

  vector<pair<int, int>> treasure(n); //{weight, value}
  rep (i, n) {
    pair<int, int> tmp;
    cin >> tmp.first >> tmp.second;
    treasure[i] = tmp;
  }
  cout << knapsack(n, w, treasure) << endl;

  return 0;
}


Measured memory_bytes: 80256
#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int A[3];
  cin >> A[0];
  cin >> A[1];
  cin >> A[2];
  int tmp = 0;
  int scost = 0;
  for(int j=0;j<2;j++){
  for(int i=0;i<2;i++){
    if(A[i] > A[i+1]){
      tmp = A[i+1];
      A[i+1] = A[i];
      A[i] = tmp;
    }
  }
  }
  cout << A[1]-A[0] + A[2]-A[1] << endl;



}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int t[100005];
int main(){
	long long int n;
	int i,j,k;
	long long int a,b,c;
	while(cin>>n){
		if(!n)break;
		a=0;
		for(i=0;i<n;i++){
			cin>>t[i];
			a+=t[i];
		}
		a/=n;
		b=0;
		for(i=0;i<n;i++){
			if(t[i]<=a)b++;
		}
		cout<<b<<endl;
	}
}



Measured memory_bytes: 3112
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	/*
		int pp=7;
		for (int i=1;i<=10000;i++) {
			String ss = String.valueOf(i);
			long count = 0;
			for (int j=0;j<ss.length();j++) {
				for (int k=j+1;k<=ss.length();k++) {
					if (Integer.parseInt(ss.substring(j,k))%pp==0) {
					count++;
					}
				}
			}
			if (count != ans(ss.length(), pp, ss)) {
				System.out.println(i);
			}
		}
		
		*/
		

		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int p = sc.nextInt();
		String s = sc.next();
	
		if (p==2 || p==5) {
			long ans = 0;
			for (int i=0;i<n;i++) {
				if ((s.charAt(i)-'0')%p==0) {
					ans+=(i+1);
				}
			}
			System.out.println(ans);
			
		} else {
			long[] count = new long[p];
			int rem = 0;
			count[0]=1;
			int digit = 1;
			for (int i=n-1; i>=0; i--) {
				rem=(rem+digit*(s.charAt(i)-'0'))%p;
				count[rem]++;
				digit=(digit*10)%p;
			}
			
			long ans = 0;
			for(int i=0;i<p;i++) {
				ans += (count[i]*(count[i]-1)/2);
			}
			System.out.println(ans);
		}

		
	}
	
	static long ans(int n, int p, String s) {
		if (p==2 || p==5) {
			long ans = 0;
			for (int i=0;i<n;i++) {
				if ((s.charAt(i)-'0')%p==0) {
					ans+=(i+1);
				}
			}
			return ans;
			
		} else {
			long[] count = new long[p];
			int rem = 0;
			count[0]=1;
			int digit = 1;
			for (int i=n-1; i>=0; i--) {
				rem=(rem+digit*(s.charAt(i)-'0'))%p;
				count[rem]++;
				digit=(digit*10)%p;
			}
			
			long ans = 0;
			for(int i=0;i<p;i++) {
				ans += (count[i]*(count[i]-1)/2);
			}
			return ans;
		}
	}
	
}




Measured memory_bytes: 28252
#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll A,B;
ll ans;
ll i, j,k,l;

ll xo(ll a){
    if(a<0)
        return 0;
    switch(a%4){
        case 1:
            a = 1;
            break;
        case 2:
            a++;
            break;
        case 3:
            a = 0;
            break;
    }
    return a;
}

int main(){
    scanf("%lld%lld", &A,&B);
    A = xo(A - 1);
    B = xo(B);
    printf("%lld", A ^ B);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+2],i;
    for(i=0; i<n; i++)cin>>a[i];
    int ans =0;
    for(int i=0; i<n-2; i++)
    {
        for(int j=i+1; j<n-1; j++)
        {
            for(int k=j+1; k<n; k++)
            {
                if(a[i]!=a[j] && a[i]!=a[k] && a[k]!=a[j]){
                if((a[i]+a[j])>a[k] && (a[i]+a[k])>a[j] && (a[j]+a[k])>a[i]) ans++;}
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>

using namespace std;

using ll = long long;


int main() {
	int N;
	cin >> N;
	vector<int> t(N), v(N);
	for (int i = 0; i < N; i++) {
		cin >> t[i];
		t[i] *= 2;
		if (i) t[i] += t[i-1];
	}
	for (int i = 0; i < N; i++) {
		cin >> v[i];
		v[i] *= 2;
	}

	vector<int> res(t.back() + 1);
	for (int i = 0; i < res.size(); i++) {
		res[i] = t.back() - i;
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = t[i]; j; j--) {
			res[j] = min(res[j], t[i] + v[i+1] - j);
		}
	}
	for (int i = 0; i < N; i++) {
		int s = i ? t[i-1] : 0;
		for (int j = s; j <= t[i]; j++) {
			res[j] = min(res[j], v[i]);
		}
	}
	res[0] = 0;
	double r = 0;
	for (int i = 1; i < res.size(); i++) {
		res[i] = min(res[i], res[i-1] + 1);
		r += res[i];
	}
	cout << fixed << setprecision(12) << r / 4 << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;

    if(s[a] != '-'){
        cout << "No" << endl;
        return 0;
    }
    for(int i = 0; i < a; i++){
        if(s[i] == '-'){
            cout << "No" << endl;
            return 0;
        }
    }
    for(int i = a+1; i < a+b+1; i++){
        if(s[i] == '-'){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
//====================== Author Info ===================
//    Khaled Alam (Ninjo)   ~   khaledalam.net@gmail.com
//======================================================
#include <bits/stdc++.h>
using namespace std;
#define  sz           size()
#define  fi           first
#define  se           second
#define  mp           make_pair
#define  pb           push_back
#define  ll           long long int
#define  ones         __builtin_popcount
#define  all(a)       (a).begin(), (a).end()
#define  iFile(a)     freopen(#a, "r", stdin)
#define  oFile(a)     freopen(#a, "w", stdout)
#define  rep(i,a,z)   for(auto i=(a);i<(z);i++)
#define  ios          ios_base::sync_with_stdio(false)
#define  tm           fprintf(stderr,"%.3f s\n",(float)clock()/1000);

int main() {
//iFile(input.txt);
//oFile(output.txt);

	int n, k, a, b;
	cin >> n >> k >> a >> b;
	if (n > k) {
		cout << (k * a) + (n - k) * b;
	} else {
		cout<<n*a;
	}

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main() {
  int n; cin >> n;
  int ans=0;
  rep(i,n){
    int l,r; cin >> l >> r;
    ans += r-l+1;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REP_S(i, n, s) for(int i = s; i < (int)(n); i++)
int main()
{
   	ios::sync_with_stdio(false);
	cin.tie(0);

	int num;
	cin >> num;

    int a[100010];
    vector<int> colorList;
    REP(i, num)   
    {
        cin >> a[i];
    }

    int maxNo = a[num - 1];
    colorList.push_back(a[num - 1]);
    for(int i = num - 2; i >= 0; --i)
    {
        if(maxNo <= a[i])
        {
            colorList.push_back(a[i]);
            maxNo = a[i];
        }
        else
        {
            
            for(int j = 0; j < colorList.size(); ++j)
            {
                if(colorList[j] > a[i])
                {
                    colorList[j] = a[i];
                    break;
                }
            }
            maxNo = colorList[colorList.size() - 1];
        }
    }

    cout << colorList.size() << endl;
	return 0;
}

Measured memory_bytes: 1276