akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>

int n, x, min, cnt;

int main() {
    scanf("%d", &n);
    min = 1e6;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x);
        min = std::min(min, x);
        if (x == min) ++cnt;
    }
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
template<class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << ", " << p.second << "}";
}
template<class t> ostream& operator<<(ostream& os, const vector<t>& v) {
  os << "{";
  rep(i, v.size()) { if(i) os << ", "; os << v[i]; }
  return os << "}";
}
// template<class t> ostream& operator<<(ostream& os, const set<t>& se) {
//   os << "{";
//   auto itr = se.begin();
//   rep(i, se.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
// template<class t, class u>
// ostream& operator<<(ostream& os, const map<t, u>& mp) {
//   os << "{";
//   auto itr = mp.begin();
//   rep(i, mp.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

vector<vector<pair<int, int> > > E; // edges
vector<int> col;
void dfs(int tmp, int par, int par_i) {
  int color = 1;
  int par_col;
  if(par == -1) par_col = -1;
  else par_col = col[par_i];
  for(auto c: E[tmp]) {
    if(c.first != par) {
      if(color == par_col) color++;
      col[c.second] = color;
      color++;
      dfs(c.first, tmp, c.second);
    }
  }
}

int main() {
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  E = vector<vector<pair<int, int> > >(N);
  col = vector<int>(N-1, 0);
  rep(i, N-1) {
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
    E[A[i]].push_back(make_pair(B[i], i));
    E[B[i]].push_back(make_pair(A[i], i));
  }
  int ans = 0;
  rep(i, N) ans = max((int)E[i].size(), ans);
  dfs(0, -1, -1);
  cout << ans << endl;
  rep(i, N-1) cout << col[i] << endl;
  return 0;
}



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

using namespace std;

int main () {
    int k;
    cin >> k;
    if (k <= 9) {
        printf ("%d\n", k);
        return 0;
    }

    queue<long long> que;
    for (int i = 1; i < 10; i++)
        que.push(i);
    long long cnt = 9, ans;
    while (cnt < k) {
        long long x = que.front();
        que.pop();
        if (x % 10 != 0) {
            cnt++;
            ans = 10 * x + (x % 10) - 1;
            que.push(ans);
        }
        if (cnt == k)
            break;
        
        // case 2
        cnt++;
        ans = 10 * x + (x % 10);
        que.push(ans);
        if (cnt == k) 
            break;
        
        // case 3
        if (x % 10 != 9) {
            cnt++;
            ans = 10 * x + (x % 10) + 1;
            que.push(ans);
        }
    }
    printf ("%lld\n", ans);
}


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

int zettai(int a, int b){
  if(a-b<=0){
    return -(a-b);
  }
  else{
    return a-b;
  }
}

int guuki(int a){
  if(a%2==0){
    return 1;
  }
  else{
    return 0;
  }
}

int main(){
  int N;
  cin >> N;
  vector<int> t(N+1,0),x(N+1,0),y(N+1,0);
  for(int i=1; i<=N; i++){
    cin >> t.at(i) >> x.at(i) >> y.at(i);
  }
  
  int time = 0, xylong = 0;
  bool ans = true;
  for(int i=1; i<=N; i++){
    time = t.at(i)-t.at(i-1);
    xylong = zettai(x.at(i),x.at(i-1))+zettai(y.at(i),y.at(i-1));
    if(xylong>time
       || (guuki(time)==1 && guuki(x.at(i)+y.at(i))!=guuki(x.at(i-1)+y.at(i-1)))
       || (guuki(time)==0 && guuki(x.at(i)+y.at(i))==guuki(x.at(i-1)+y.at(i-1)))){
      cout << "No" << endl;
      ans = false;
      break;
    }
  }
  if(ans) cout << "Yes" << endl;
}

Measured memory_bytes: 1408
#include<stdio.h>
#define NOT_FREE 1
#define FREE 0
int ar[8][8];
int col[8],row[8],dpos[15],dneg[15],flag=0,scol[8],srow[8],sflag=0;
void putQueen(int,int);
void printBoard(void);
int main(){
  int j,n,a,b,i;
  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
    ar[i][j]=FREE;
    }
    col[i]=FREE;
    row[i]=FREE;
    dpos[i]=FREE;
    dneg[i]=FREE;
  }

  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d",&a,&b);
    ar[a][b]=NOT_FREE;
  
  }
  putQueen(0,7);
  return 0;

}
void putQueen(int i,int n){
  int j,k;
  if(i==n+1){
    printBoard();
    return;
  }
  for(j=0;j<=n;j++){
    if(col[j]==NOT_FREE||dpos[i+j]==NOT_FREE||dneg[i-j+n]==NOT_FREE){
      continue;
    }
   

    row[i]=j;
    col[j]=NOT_FREE;
    dpos[j+i]=NOT_FREE;
    dneg[i-j+n]=NOT_FREE;
    putQueen(i+1,n);
    
    col[j]=FREE;
    dpos[i+j]=FREE;
    dneg[i-j+n]=FREE;
  }
}
void printBoard(void){
  int i,j;
  /* for(i=0;i<8;i++){
    for(j=0;j<8;j++){
      if(col[i]==NOT_FREE){
	if(col[j]==NOT_FREE){
	  ar[i][j]=NOT_FREE;
	}
      }
    }
  }
  */
  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
      if(ar[i][j]==1){
	if(row[i]!=j)return;
      }
    }
  }
  
  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
      if(row[i]==j){
	printf("Q");
      }
      else printf(".");
    }
    printf("\n");
  }
}



Measured memory_bytes: 2112
w, h, n = map(int, input().split())
xya = [0] * n
for i in range(n):
    xya[i] = list(map(int, input().split()))

left_x = bottom_y = 0
right_x = w
top_y = h
for x, y, a in xya:
    if a == 1:
        left_x = max(left_x, x)
    elif a == 2:
        right_x = min(right_x, x)
    elif a == 3:
        bottom_y = max(bottom_y, y)
    else:
        top_y = min(top_y, y)
if right_x <= left_x or top_y <= bottom_y:
    print(0)
else:
    print((right_x - left_x) * (top_y - bottom_y))

Measured memory_bytes: 3064
//
// 
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define is_in(i, s) (s.find(i) != s.end())
#define all(x) (x).begin(),(x).end()
#define outl(x) cout<<x<<endl
#define outsp(x) cout<<x<<" "
typedef long long ll;
typedef pair<int,int> P;


#define MAX_N 105


int main() {
	int n,k;
	bool a[MAX_N];
	memset(a,0,sizeof(a));
	cin >> n >> k;
	int cnt = n;
	rep(i,k){
		int d;
		cin >> d;
		rep(j,d){
			int an;
			cin >> an;
			if(!a[an]){
				a[an] = true;
				cnt--;
			}
		}
	}
	outl(cnt);
    return 0;
}



Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

	Scanner sca = new Scanner(System.in);
	long n = sca.nextLong();
	long a = sca.nextLong();
	long b = sca.nextLong();
	long biga, bigb;

	if((b-a) % 2 == 0) {
		System.out.println((b-a) / 2);
		return;
	}

	biga = a-1;
	bigb = n-b;

	if(biga < bigb) {
		a = a - biga;
		b = b - biga-1;
		System.out.println(biga + 1 + ((b-a) / 2));
	}
	else {
		b = b + bigb;
		a = a + bigb;
		System.out.println(bigb + 1 + ((b-a) / 2));
	}
	sca.close();
	}
}

Measured memory_bytes: 23508
#include<bits/stdc++.h>
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define ll long long
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
using namespace std;
const int N=1e5+5;
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*10+ch-'0';ch=getchar();}
	return x*f;
}
int a[N],b[N],n,ans;
int main(){
#ifdef Devil_Gary
	freopen("in.txt","r",stdin);
#endif
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),a[i]+=a[i-1];
	for(int i=1;i<=n;i++) b[i]=read(); 
	for(int i=n;i;i--) b[i]+=b[i+1];
	for(int i=1;i<=n;i++) ans=max(ans,a[i]+b[i]);
	cout<<ans<<endl; 
}


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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vll;

int main() {
    string s;
    cin >> s;
    ll ans = 700;
    for (auto &c : s) {
        if (c == 'o') {
            ans += 100;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

#define min_3(a, b, c) min(a, min(b, c))
using namespace std;

const int oo = 1e9;
int A, B, C;
vector <int> bamboo;

int dfs(int N, int a, int b, int c)
{
    if(N == 0)
        return (min_3(a, b, c) > 0 ? abs(a - A) + abs(b - B) + abs(c - C) - 30: oo);

    int do_nothing = dfs(N - 1, a, b, c);
    int add_a = dfs(N - 1, a + bamboo[N], b, c) + 10;
    int add_b = dfs(N - 1, a, b + bamboo[N], c) + 10;
    int add_c = dfs(N - 1, a, b, c + bamboo[N]) + 10;

    int minimum_adding = min_3(add_a, add_b, add_c);
    int minimum = min(do_nothing, minimum_adding);

    return minimum;
}

int main()
{
    int no_of_elements;
    cin >> no_of_elements >> A >> B >> C;

    bamboo.resize(no_of_elements + 1);
    for(int i = 1; i <= no_of_elements; i++)
        cin >> bamboo[i];

    int minimum_cost = dfs(no_of_elements, 0, 0, 0);
    cout << minimum_cost;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    char n[5];
    scanf("%s", n);
    if (n[0] == n[1] && n[0] == n[2])
        puts("Yes");
    else if (n[1] == n[2] && n[1] == n[3])
        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 reader = new Scanner(System.in);

    int n = reader.nextInt();
    int tScore = 0, hScore = 0;
    for (int i = 0; i < n; i++) {
      String tStr = reader.next();
      String hStr = reader.next();
      if (tStr.compareTo(hStr) > 0) {
        tScore += 3;
      }
      else if (tStr.compareTo(hStr) == 0) {
        tScore += 1;
        hScore += 1;
      }
      else {
        hScore += 3;
      }
    }
    System.out.println(tScore + " " + hScore);
  }
}

Measured memory_bytes: 30372
import itertools

n = int(input())
d = {'M':0, 'A':1, 'R':2, 'C':3, 'H':4}
h = [0, 0, 0, 0, 0]
for _ in range(n):
  name = input()
  if name[0] in d.keys():
    h[d[name[0]]] += 1

ans = 0
for i, j, k in itertools.combinations([0, 1, 2, 3, 4], 3):
  ans += h[i] * h[j] * h[k]
print(ans)

Measured memory_bytes: 9160
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int a,b;

int main()
{
	scanf("%d%d",&a,&b);
	if(a>9||b>9)
	{
		puts("-1");
	}
	else
	{
		printf("%d\n", a*b);
	}
	return 0;
}

Measured memory_bytes: 256
from collections import deque

S = list(input())
Q = int(input())
d = deque(S)
flag = -1
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag *= -1
    else:
        f = int(q[1])
        c = q[2]
        if flag == -1 and f == 1 or flag == 1 and f == 2:
            d.appendleft(c)
        else:
            d.append(c)
d = list(d)
if flag == 1:
    d = d[::-1]

print(''.join(d))


Measured memory_bytes: 10996
from collections import deque
H,W,N=map(int,input().split())
e='X'*(W+2)
M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
m=(1,-1,W+2,-W-2)
def f(s,g):
 p,t=s,0
 q=deque()
 b=[1]*len(M);b[s]=0
 while 1:
  for d in m:
   n=p+d
   if'X'!=M[n]and b[n]:
    if M[n]==g:return(n,t+1)
    b[n]=0;q.append([n,t+1])
  p,t=q.popleft()
s=M.find('S')
a=0
for i in range(1,N+1):
 s,t=f(s,str(i))
 a+=t
print(a)


Measured memory_bytes: 14952
n, m = map(int,input().split())

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

ans = 1000000000000000
for i in range(2 ** n):
    check = 0
    ac = 0
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            check += a[j][0] * 100 * (j + 1) + a[j][1]
            tmp += a[j][0]
        
        if check >= m:
            ans = min(ans, tmp)

        else:
            for k in reversed(range(n)):
                if not (i >> k) & 1:
                    ac = -(-(m - check) // ((k + 1) * 100))
                    if ac < a[k][0]:
                        ans = min(ans, ac + tmp)

print(ans)

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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<string, vector<string>, greater<string> > PQ_ASK;

#include <iostream>
#include <vector>

using namespace std;
const int ROW_MAX = 100;

int main() {
    int n;
    cin >> n;
    vector<vector<char>> a(n, vector<char>(n));
    rep(i, n) rep(j, n) cin >> a[i][j];

    auto check = [&](int x) {
        vector<vector<char>> b(n, vector<char>(n));
        rep(i, n) rep(j, n) {
                b[i][j] = a[(i + x) % n][j];
            }
        rep(i, n) rep(j, n) {
                if (b[i][j] != b[j][i]) return false;
            }
        return true;
    };

    int ans = 0;
    rep(x, n) {
        if (check(x)) ans++;
    }
    cout << ans * n << endl;
}




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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;


int main(){
	int n;
	int a[100],b[100];
	cin>>n;
	for (int i = 0; i < n; i++){
		cin>>a[i];
	}
	for (int i = 0; i < n; i++){
		cin>>b[i];
	}

	int ans=0;
	int sum=0;
	for (int i = 0; i < n; i++){
		sum+=a[i];
		int und=0;
		for (int j = i; j < n; j++){
			und+=b[j];
		}
		ans=max(ans,sum+und);
	}

	cout<<ans<<endl;

	return 0;
}
	

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

int main() {
  vector<int> vec(3);
  for(int i=0;i<3;i++){
    cin>>vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
    cout<<vec.at(0)*vec.at(1)/2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define  LL long long

int main()
{
	string s;
	int k;
	cin>>s>>k;
	for(int i=1;i<=k&&i<=s.length();i++){
		if(s[i-1]!='1'){
			printf("%c\n",s[i-1]);
			return 0;
		}
	}
	printf("1");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b) - 1; (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    int n,l;
    cin >> n >> l;
    if (l >=  0) {
        cout << (l + l + n - 1) * (l + n - 1 - l + 1) / 2 - l<< endl;
    }else if(n + l - 1 <= 0){
        cout << (l + l + n - 1) * (l + n - 1 - l + 1) / 2 - (l + n - 1)  << endl;
    }else{
        cout << (l + l + n - 1) * (l + n - 1 - l + 1) / 2 << endl;
    }
    return 0;
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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; }

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  double l; cin>>l;
  double t=l/3.0;
  double r=l-t-t;
  double ans=t*t*r;
  coutd(ans);
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>

#define in std::cin
#define out std::cout

int32_t N;
int64_t sum = 0;
int64_t num = 0;
int32_t a[100000];
int32_t diff[100000];//a[i]-a[i+1]
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);

	in >> N;
	int64_t mod = ((int64_t)(N)*(N+1))/2;
	sum = 0;
	for (int32_t i = 0; i < N; ++i)
	{
		in >> a[i];
		sum += a[i]; num += sum / mod; sum %= mod;
	}
	if (sum != 0) { out << "NO" << std::endl; return 0; }
	if (N == 1) { out << "YES" << std::endl; return 0; }

	for (int32_t i = 0; i < N-1; ++i)
	{
		diff[i] = a[i] - a[i + 1];
	}
	diff[N - 1] = a[N - 1] - a[0];
	std::sort(diff, diff + N, std::greater<>{});
	int64_t total_operation = 0;
	for (int32_t i = 1; i < N; ++i)
	{
		if((diff[0] - diff[i]) % N){ out << "NO" << std::endl; return 0; }
		total_operation += (diff[0] - diff[i])/ N;
	}
	if(total_operation == num){ out << "YES" << std::endl; return 0; }

	for (int32_t i = 1; i < N; ++i)
	{
		total_operation += (i - (N-i))*
			((diff[i-1] - diff[i])/N);
		if (total_operation == num) { out << "YES" << std::endl; return 0; }
	}
	out << "NO" << std::endl; return 0;


	return 0;
}
#endif


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
using namespace std;

int main(void) {
    int input;
    int mode[1000];
    memset(mode, 0, sizeof(mode));
    int max = INT_MIN;
    while(cin >> input) {
        mode[input]++;
        if(mode[input] > max) max = mode[input];
    }
    for(int r = 0; r < 1000; r++) {
        if(mode[r] == max) cout << r << endl;
    }
    
    return(0);
}

Measured memory_bytes: 1164
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    cout << max(0LL, ( b * ( n - 1 ) + a  ) -  ( b + a * ( n - 1 ) ) + 1 ) << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int n;
ll mem[MAXN][2];
ll a[MAXN];
ll solve(int i,int f)
{

if(i == n)
{
    if(f) return -1e9;
    return 0;
}

ll &ret = mem[i][f];

if(ret != -1) return ret;
ret = 0;
ll p1  = 0 , p2 = 0;
if(f) p1 = solve(i + 1 , 0) - a[i];
else p1 = solve(i + 1 , 0) + a[i];
if(!f) p2 = solve(i + 1 , 1) - a[i];
else p2 = solve(i + 1 , 1) + a[i];
ret = max(p1,p2);
return ret;

}

int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++) cin >> a[i];
	memset(mem,-1,sizeof(mem));
    cout << solve(0,0) << '\n';
}

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

class UnionFindTree {
  vector<int> parent, rank;

  int find(int x) {
    if(parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

public:

  UnionFindTree(int size) {
    parent = vector<int>(size);
    rank = vector<int>(size, 0);
    for(int i = 0; i < size; i++) parent[i] = i;
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y)return;

    if(rank[x] < rank[y]) {
      parent[x] = y;
    } else {
      parent[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int N, M;
vector<int> p;

int main () {
  cin >> N >> M;
  p.resize(N);
  rep(i,N) {
    cin >> p[i];
    p[i]--;
  }

  auto t = new UnionFindTree(N);
  rep(i,M) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    t->unite(x, y);
  }

  int ans = 0;
  rep(i,N) {
    ans += t->same(i, p[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> vp(51); 
vector<bool> cashed(51);

pair<ll,ll> burger1(int level){
    if(cashed.at(level)) return vp.at(level);
    pair<ll,ll> p;
    if(level == 0){
        p = {1,1};
    }else{
        auto lvm1 = burger1(level-1);
        p = {lvm1.first*2+3, lvm1.second*2+1};
    }
    vp.at(level) = p;
    cashed.at(level) = true;
    return p;
}

ll burger(int level, ll eat){
    if(level==0) {
        if(eat == 0) return 0;
        else return 1;
    }
    ll tot=0;
    ll rest = eat;
    if(rest <= 0) return tot;

    // top ban
    rest--;
    if(rest <= 0) return tot;
    
    // level-1
    if(rest < vp.at(level-1).first){
        return burger(level-1,rest) + tot;
    }
    rest -= vp.at(level-1).first;
    tot += vp.at(level-1).second;
    if(rest <= 0) return tot;

    // center pan
    rest--;
    tot++;
    if(rest <= 0) return tot;

    // level-1
    if(rest < vp.at(level-1).first){
        return burger(level-1,rest) + tot;
    }
    rest -= vp.at(level-1).first;
    tot += vp.at(level-1).second;
    
    return tot;
}

int main(){
    ll n,x;
    cin >> n >> x;
    burger1(n);
    // rep(i,n+1) cout << vp.at(i).second << endl;
    cout << burger(n,x) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int a[3],m[3];
	while(true){
		for(int i=0;i<3;i++)cin>>a[i]>>m[i];
		if(a[0]==0)break;
		int cnt[3];
		for(int i=0;i<3;i++){
			cnt[i]=1;
			int x=1;
			while(true){
				x=x*a[i]%m[i];
				if(x==1)break;
				cnt[i]++;
			}
		}
		long long s=min(cnt[0],cnt[1]);
		while(true){
			bool ok=true;
			for(int i=0;i<2;i++)if(cnt[i]%s!=0)ok=false;
			if(ok)break;
			s--;
		}
		s=cnt[0]*cnt[1]/s;
		long long k;
		if(s<cnt[2])k=s;else k=cnt[2];
		while(true){
			bool ok=true;
			if(s%k!=0||cnt[2]%k!=0)ok=false;
			if(ok)break;
			k--;
		}
		cout<<s*cnt[2]/k<<endl;
	}
	return 0;
}

Measured memory_bytes: 1156
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        int[] pi = LineInt();
        long K = 30000;
        //aは固定してbだけ考える
        long[] a = Enumerable.Range(0, N).Select(v => (v + 1) * K).ToArray();
        long[] b = Enumerable.Range(0, N).Select(v => (N - v) * K).ToArray();

        for (int i = 0; i < N; i++)
        {
            b[pi[i] - 1] -= (N - i - 1);
        }
        a.ToList().ForEach(v => Console.Write(v + " "));
        Console.WriteLine();
        b.ToList().ForEach(v => Console.Write(v + " "));
        Console.WriteLine();
    }

    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}
public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 23516
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long int
#define phi 1.6180339
#define rep(i,n) for(auto i=0;i<(n);i++)
#define endl "\n"
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define op1 cin.tie(NULL)
#define op2 cout.tie(NULL)
#define op3 std::ios_base::sync_with_stdio(false)
#define MAXX 1000001
using namespace std;
vector<int> arr(MAXX);
void trozen()
{
    int n;
    cin>>n;
    int arr[n][3];
    rep(i,n) cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    int dp[n][3];
    dp[0][0]=arr[0][0];dp[0][1]=arr[0][1];dp[0][2]=arr[0][2];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            dp[i][j]=INT_MIN;
            for(int k=0;k<3;k++)
            {
                if(j!=k) dp[i][j]=max(dp[i][j],dp[i-1][k]+arr[i][j]);
            }
        }
    }
    int ans=max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
    cout<<ans<<endl;
}
int32_t main()
{
    op1;op2;op3;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    trozen();
    return 0;
}


Measured memory_bytes: 15552
#include<iostream>
#include<vector>
#include<cmath>
#include<utility>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == 5 && b == 7 && c == 5)
		cout << "YES" << endl;
	else if (a == 7 && b == 5 && c == 5)
		cout << "YES" << endl;
	else if (a == 5 && b == 5 && c == 7)
		cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c;
	scanf("%d%d",&a,&b);
	for(c=1;c<=3;c++)
		if(a*b*c%2==1)
		{
			printf("Yes");
			return 0;
		}
	printf("No");
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#define size 100001

int N,M;
int*dist[size];
int city[size];
int qu[size];
int dist_s[size];

void set(){
  int a,b;
  for(int i=0;i<N;i++){
    city[i]=-1;
    dist_s[i]=0;
  };
  city[0]=0;
  for(int i=0;i<M;i++){
    scanf("%d %d",&a,&b);
    a--;b--;
    dist[a]=realloc(dist[a],sizeof(int)*(dist_s[a]+1));
     dist[a][dist_s[a]]=b;//得出由a城到b城的所有可能路径
      dist_s[a]++;
    dist[b]=realloc(dist[b],sizeof(int)*(dist_s[b]+1));
     dist[b][dist_s[b]]=a;
      dist_s[b]++;
  };
};

void sys(){
  int tar=0,nm=0,ji=0;
  while(1){
    for(int i=0;i<dist_s[tar];i++){//到目标城市的所有可能
      if(city[dist[tar][i]]!=-1)continue;
      city[dist[tar][i]]=tar+1;//目标城市深度
      qu[nm]=dist[tar][i];//到达深度的各城市队列
      nm++;
    };
    if(nm==ji)break;
    tar=qu[ji];//计算队列中第一个城市
    ji++;
  };
};
    
int main(void){
   scanf("%d%d",&N,&M);
   set();
   sys();
   printf("Yes\n");
   for(int i=1;i<N;i++){
     printf("%d\n",city[i]);
   };
  
  return 0;
}

Measured memory_bytes: 8472
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void){
    int L, R, d;
    cin >> L >> R >> d;

    int cnt = 0;
    for(int i = L; i <= R; i++){
        if(i % d == 0) cnt++;
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>
 
int main() {
  int hp, n;
  scanf("%d %d", &hp, &n);
  for (int i = 1;i <= n;i ++) {
   	int dat;
    scanf("%d", &dat);
    hp -= dat;
  }
  if (hp <= 0) printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
static const ll maxLL = (ll) 1 << 62;
const ll MOD = 1000000007, INF = 1e18;

template<typename T1, typename T2>
bool pairCompare(const pair<T1, T2> &firstElof, const pair<T1, T2> &secondElof) {
    return firstElof.second > secondElof.second;
}

int mapMaxValue(std::map<ll, int> m) {
    int max = 0;
    for (std::map<ll, int>::iterator it = m.begin(); it != m.end(); it++) {
        if (max < it->second) max = it->second;
    }
    return max;
}

int main(void) {
    int n;
    cin >> n;
    vi a(n, 0), b(n,99999999);
    for (int i = 0; i < n - 1; ++i) {
        cin >> b[i];
    }
    a[0] = b[0];
    for (int i = 0; i < n - 1; ++i) {
        a[i] = min(a[i], b[i]);
        a[i + 1] = b[i];
    }
    ll ans = 0;
    for (auto e: a) {
        ans += e;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
// in the name of Allah

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define ll long long
#define double long double
#define sz(x) ((int) (x.size()))

#define fr first
#define se second

const ll mod = 1000000009;

inline ll add(ll a, ll b) {
	a += b;
	if(a >= mod) return a - mod;
	return a;
}

inline ll mul(ll a, ll b) {
	a *= b;
	if(a >= mod) return a % mod;
	return a;
}

inline ll power(ll a, ll b) {
	ll p = 1;
	while(b) {
		if(b&1) p = mul(p, a);
		a = mul(a, a);
		b /= 2;
	}
	return p;
}

inline ll power(ll a, ll b, ll m) {
	ll p = 1;
	while(b) {
		if(b&1) p = (p * a) % m;
		a = (a * a) % m;
		b /= 2;
	}
	return p;
}

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

	int n, k;
	string s;
	cin >> n >> k >> s; k--;
	s[k] += 'a' - 'A';
	cout << s << endl;

	return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;
const int N=1e5+5;

namespace utils{
	template <class T> inline void apn(T &x,const T y){x=x<y?x:y;}
	template <class T> inline void apx(T &x,const T y){x=x<y?y:x;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=(c=='-')&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

int main(){
#ifdef LOCAL
	freopen("range.in","r",stdin);
	freopen("range.out","w",stdout);
#endif
	int n=nxi(),ans=0;
	for(int i=1,l=1; i<=n; ++i){
		if(i!=nxi()){
			if(l<i) ans+=(i-l+1)>>1;
			l=i+1;
		}
		else if(i==n){
			ans+=(i-l+2)>>1;
		}
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repbit(bit,n) for (int bit = 0; bit < (1<<n); bit++)
using namespace std;
typedef long long ll;

//const int INF = 1001001001;
//const ll INF18 = 1000000000000000000;
const ll INF15 = 1000000000000000;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a[i];

	ll ans = 0;
	rep(i,n - 1) {
		int diff = a[i] - a[i + 1];
		if (diff > 0) {
			ans += diff;
			a[i + 1] += diff;
		}
	}
	cout << ans << endl;
	return 0;
}


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


int main()
{
	int a, b, c, w;
	cin >> a;
	cin >> b;
	cin >> c;

	if (a > b){
		w = a;
		a = b;
		b = w;

		if (b > c){
			w = b;
			b = c;
			c = w;
		}
		if (a > b){
			w = a;
			a = b;
			b = w;
		}
	}
	else{
		if (b > c){
			w = b;
			b = c;
			c = w;

			if (a > b){
				w = a;
				a = b;
				b = w;
			}
		}
	}

	cout << a << " " << b << " " << c << endl;
	
	return 0;
}


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

int main() {
    int a,b;cin >> a >> b;
    string s;cin >> s;
    b = b-1;
    if(s[b]=='A'){
        s[b] = 'a';
    }else if(s[b]=='B'){
        s[b] = 'b';
    }else{
        s[b] = 'c';
    }

    cout << s << endl;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  std::vector<ll> x(5);
  IN(x[0], x[1], x[2], x[3], x[4]);

  REP(i,5){
    if(x[i]==0){
      OUT(i+1);
      break;
    }
  }

  return 0;
}

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

int main(){
    int n, m, i, j, v;
    int a[100][100] = {0};
    int b[100] = {0};
    int c[100] = {0};

    cin >> n >> m;
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    for(j=0;j<m;j++) {
        cin >> b[j];
    }
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            c[i] += a[i][j] * b[j];
        }
    }
    for(i=0;i<n;i++) {
        cout << c[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

struct Graph {
    enum Color {WHITE, GRAY, BLACK};
    vector<vector<int>> adj;
    vector<Color> color;
    Graph(int n) {
        adj.assign(n, vector<int>());
        color.assign(n, WHITE);
    }
};

int dfs(Graph& g, int u)
{
    bool completed = true;
    for (auto c : g.color) {
        if (c == Graph::WHITE) {
            completed = false;
            break;
        }
    }
    if (completed) {
        return 1;
    }
    int ans = 0;
    for (auto v : g.adj[u]) {
        if (g.color[v] == Graph::WHITE) {
            g.color[v] = Graph::BLACK;
            ans += dfs(g, v);
            g.color[v] = Graph::WHITE;
        }
    }
    return ans;
}

int main()
{
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g.adj[a - 1].push_back(b - 1);
        g.adj[b - 1].push_back(a - 1);
    }

    g.color[0] = Graph::BLACK;
    cout << dfs(g, 0) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <cmath>

int main(int argc, char const *argv[]) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    if (A + B >= C) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<string> split(string str, char del) {
    int first = 0;
    int last = str.find_first_of(del);

    vector<string> result;

    while (first < str.size()) {
        string subStr(str, first, last - first);

        result.push_back(subStr);

        first = last + 1;
        last = str.find_first_of(del, first);

        if (last == string::npos) {
            last = str.size();
        }
    }

    return result;
}

int main(){
  string s;

  cin >> s;
  vector<string> strs = split(s,'/');

  int year = stoi(strs[0]);
  int month = stoi(strs[1]);
  int day = stoi(strs[2]);

  if(year > 2019){
    cout << "TBD" << endl;
    return 0;
  }

  if(month > 4){
    cout << "TBD" << endl;
    return 0;
  }

  if(day > 30){
    cout << "TBD" << endl;
    return 0;
  }

  cout << "Heisei" << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Text.RegularExpressions;

class C
{
	static void Main()
	{
		Console.ReadLine();
		var s = Console.ReadLine();

		for (var c = 'a'; c <= 'z'; c++)
			s = Regex.Replace(s, $"{c}+", $"{c}");
		Console.WriteLine(s.Length);
	}
}


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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define rall(v) v.rbegin(), v.rend()
#define all(v) v.begin(), v.end()
#define PB push_back
#define F first
#define S second

typedef unsigned long long llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int INF = 1e9+10;
const ll MOD = 1e9+7;

void solve(){
	int n, p; cin >> n >> p;
	string s; cin >> s;

	if(p == 2){
		ll ans = 0;
		for(int i = 0; i < n; i++){
			if((s[i]-'0')%2 == 0){
				ans += i+1;
			}
		}
		cout << ans << '\n';
		return;
	}

	if(p == 5){
		ll ans = 0;
		for(int i = 0; i < n; i++){
			if(s[i] == '5' || s[i] == '0'){
				ans += i+1;
			}
		}
		cout << ans << '\n';
		return;
	}

	map<int,int> m;
	ll ans = 0;
	ll atual = 0;
	ll p10 = 1;
	m[0] = 1;
	for(int i = n-1; i>=0; i--){
		atual = ((s[i]-'0')*p10 + atual)%p;
		ans += m[atual];
		m[atual]++;
		p10 = (p10 * 10) % p;
	}
	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int t=1; //cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

Measured memory_bytes: 916
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[] a = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
            sum += a[i];
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (a[i] / (double) sum >= 1 / (4.0 * M)) {
                count++;
            }
        }
        

        System.out.print(count >= M ? "Yes" : "No");

        scanner.close();
    }
}

Measured memory_bytes: 24148
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define endl            "\n"
#define forn(i,x,n)     for(int i=x; i<n; i++)
#define forit(it, m)    for(decltype(m)::iterator it = m.begin(); it!=m.end(); ++it)
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#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 setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#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--)
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;


void zeus()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int fast_pow(long long base, long long n, long long M)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return base;
    long long halfn = fast_pow(base, n / 2, M);
    if (n % 2 == 0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}

int findMMI_fermat(int n, int M)
{
    return fast_pow(n, M - 2, M);
}

int32_t main() {

    zeus();

    int n; cin >> n;

    set<string> s;

    forn(i, 0, n) {
        string a; cin >> a;
        s.insert(a);
    }
    cout << s.size() << endl;
}




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

int main(){
  int N; cin >> N;
  vector<pair<int,int>> A(N);
  
  for(int i = 0; i < N; i++){
    A[i].second = i+1;
    cin >> A[i].first;
  }
  
  sort(A.begin(), A.end());
  
  for(int i = 0; i < N;i++){
    cout << A[i].second << " ";
  }
  
  return 0;
}

Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int MOD = 1000000007;
const int INF = 1001001001;

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}

#define rep(i, n)  for(int i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()
int table[10][10];

int main() {
    int n;
    int ans = 0;
    cin >> n;
    char s[n];
    cin >> s;
    for(int i = 0; i < n-2; i++) {
        for(int j = i + 1; j < n-1; j++) {
            if(table[int(s[i]-'0')][int(s[j]-'0')] == 0){
                table[int(s[i]-'0')][int(s[j]-'0')] = 1;
                set<char> ch;
                for(int k = j + 1; k < n; k++) {
                    ch.emplace(s[k]);
                }
                ans += ch.size();
            }
        }
    }

    cout << ans << endl;
}

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

void solve() {
    int R;
    cin >> R;
    if (R < 1200) cout << "ABC";
    else if (R < 2800) cout << "ARC";
    else cout << "AGC";
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    int n, x;
    while (cin >> n >> x, n || x) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int k = x - i - j;
                if (k <= n && k > i && k > j) cnt++;
            }
        }
        cout << cnt << endl;
    }
}


Measured memory_bytes: 3016
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef vector < int > vi;

const int N = 2e5 + 500;

int x, y, n;
ll L = 0, R = 0, A[N], sol = 1e18;

ll labs(ll x){
	return x > 0LL ? x : -x;
}

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%lld", A + i), R += A[i];
	}
	R -= A[0], L += A[0];
	for(int i = 1;i < n;i++){
		sol = min(sol, abs(L - R));
		L += A[i], R -= A[i];
	}
	printf("%lld\n", sol);
	return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int dp[N][N];
string a,b;
void LCS(){
    for(int i = 1;i <= (int) a.size();i++){
        for(int j = 1;j <= (int) b.size();j++){
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
}
void find_LCS(){
    int s1 = (int) a.size(),s2 = (int) b.size();
    string wyn;
    while(s1 > 0 && s2 > 0){
        if(a[s1-1] == b[s2-1]){
            wyn += a[s1-1];
            s1--;s2--;
        }
        else if(dp[s1-1][s2] > dp[s1][s2-1]) s1--;
        else s2--;
    }
    reverse(wyn.begin(),wyn.end());
    cout << wyn;
}
int main(){
    cin >> a >> b;
    LCS();
    find_LCS();
    return 0;
}

Measured memory_bytes: 35456
using System;
using System.Linq;

namespace ABC155A
{
    class Program
    {
        static void Main(string[] args)
        {
            var ABC = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            Console.WriteLine(ABC.Distinct().Count() == 2 ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 13396
# 13
import sys
import numpy as np


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n = I()
a = np.array(LI())
b = np.array(LI())
diff = a - b
pos = [diff[i] for i in range(len(diff)) if diff[i] > 0]
neg = [diff[i] for i in range(len(diff)) if diff[i] < 0]
if sum(pos) + sum(neg) < 0:
    print(-1)
    exit()

# if len(neg) == 0:
#     print(0)
#     exit()

ans = len(neg)
s_neg = sum(neg)
sort_pos = sorted(pos)[::-1]
for elem in sort_pos:
    if s_neg < 0:
        ans += 1
        s_neg += elem
    else:
        break
print(ans)


Measured memory_bytes: 39648