akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/

int main(){
    string s; cin >> s;
    int count = 0;

    for(int i = 0, j = s.size() - 1; i < j;){
        if(s[i] == s[j])i++, j--;
        else if(s[i] == 'x'){
            count++;
            i++;
        }else if(s[j] == 'x'){
            count++;
            j--;
        }else{
            cout << -1 << endl;
            return 0;
        } 
    }
    cout << count << endl;
}

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

using namespace std;

const int N=2e5;

int cnt[N+2],parent[N+2];

int FindParent(int n)
{
    if(parent[n] == n)return n;
    return parent[n]=FindParent(parent[n]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int i,m,n,x,y,ans=0;
    cin >> n >> m;
    for(i=1;i<=n;i++)parent[i]=i;
    while(m--)
    {
        cin >> x >> y;
        x=FindParent(x);
        y=FindParent(y);
        if(x != y)parent[y]=x;
    }
    for(i=1;i<=n;i++)
    {
        x=FindParent(i);
        ++cnt[x];
        ans=max(ans,cnt[x]);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;
random_device rd;
mt19937 mt(rd());

int d;
vi c;
vvi s;

vi res;
vvi last;

vi ans, test;
ll mx = 0;

ll score(vi t, int st = 0) {

	rep(i, d) {

		ll plus = 0;
		plus += s[i][t[i]];
		rep_lr(j, st, 26) {
			if (j == t[i])last[i + 1][t[i]] = i + 1;
			else last[i + 1][j] = last[i][j];
			plus -= c[j] * ((ll)i + 1 - last[i + 1][j]);
		}

		res[i + 1] = res[i] + plus;

	}
	return res[d - 1];

}

void init() {

	c.resize(26);
	s.resize(d, vi(26));
	last.assign(d + 1, vi(26, 0));
	res.resize(d + 1, 0);
	ans.resize(d);
	test.resize(d);

}

int main() {

	cin >> d;

	double time = (double)clock() / CLOCKS_PER_SEC;
	
	init();
	rep(i, 26)cin >> c[i];
	rep(i, d)rep(j, 26)cin >> s[i][j];

	vi first(d);
	rep(i, d)first[i] = mt() % 26;

	rep(i, d)ans[i] = test[i] = first[i];
	mx = score(first);

	int loop = 0, rec = 0;
	while (((double)clock() / CLOCKS_PER_SEC) - time < 1.8) {

		int change = mt() % d;
		test[change] = mt() % 26;
		ll re = score(test, change);
		if (mx < re) {
			mx = re;
			rep(i, d)ans[i] = test[i];
			rec++;
		}

		loop++;
	}

	for (auto x : ans)cout << x + 1 << endl;
}

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

int main(){
   int l,r,d;
   cin >> l >> r >> d;
   int ans = 0;
   for(int i=l;i<=r;++i){
       if(i%d == 0) ans++;
   }
   cout << ans << endl;
}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
   long long a,b,c,d;
   long long arr[4];
   long long max;

   cin>>a>>b>>c>>d;
   arr[0] = a*c;
   arr[1] = a*d;
   arr[2] = b*c;
   arr[3] = b*d;
  
   max = arr[0];
   for (int i = 1; i < 4; i++)
   {  
      if(max < arr[i])
         max = arr[i];
   }
     cout<<max<<endl; 
   


}

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

int main(){
  int n; cin >> n;
  vector<int> ans(26,100);
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    vector<int> cnt(26);
    for(int j = 0; j < s.size(); j++){
      int idx = s[j] - 'a';
      cnt[idx]++;
    }
    for(int j = 0; j < 26; j++){
      ans[j] = min(ans[j], cnt[j]);
    }
  }
  for(int i = 0; i < 26; i++){
    char c = 'a' + i;
    for(int j = 0; j < ans[i]; j++){
      cout << c;
    }
  }
}
    
    

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;


int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	if (k > a) {
		k -= a;
		a = 0;
		b = max(0LL, b - k);
	}
	else {
		a -= k;
	}
	cout << a << ' ' << b;
}

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

int dx[12] = { 1,0,-1,0,1,-1,-1,1,2,0,-2,0 };
int dy[12] = { 0,-1,0,1,-1,-1,1,1,0,-2,0,2 };

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	vector<vector<int>> paper(10, vector<int>(10, 0));
	int x, y, s; char c;
	int b = 100, m = 0;
	while (cin >> x >> c >> y >> c >> s) {
		if (paper[x][y] == 0) b--;
		//paper[x][y]++;
		m = max(++paper[x][y], m);
		int l;
		if (s == 1) l = 4;
		else if (s == 2)l = 8;
		else l = 12;

		for (int i = 0; i < l;i++) {
			if (x + dx[i] < 0 || x + dx[i] > 9 || y + dy[i] < 0 || y + dy[i] > 9) continue;
			if (paper[x + dx[i]][y + dy[i]] == 0)b--;
			m = max(++paper[x + dx[i]][y + dy[i]],m);
		}
	}
	cout << b << endl << m << endl;
}

Measured memory_bytes: 3120
A,B = gets.split(" ").map{|i|i.to_i}
S = gets
if /^[0-9]+$/ =~ S[0..A-1] && S[A] == "-" && /^[0-9]+$/ =~ S[(A+1)..S.length-1]
    puts "Yes"
else
    puts "No"
end



Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
int main(void){
    int n;
    cin>>n;
    vvi day={{0,20,19,20,19,20,19,20,19,20,19,},{0,20,20,20,20,20,20,20,20,20,20,}};
    partial_sum(all(day[0]),day[0].begin());
    partial_sum(all(day[1]),day[1].begin());
    auto f=[day](int y,int m,int d){int p=0;rep(i,y-1){p+=day[(i+1)%3==0][10];}p+=day[y%3==0][m-1]+d;return p;};
    rep(lp,n){
        int y,m,d; cin>>y>>m>>d;
        cout<<f(1000,1,1)-f(y,m,d)<<endl;
    }
}

Measured memory_bytes: 3160
#include<iostream>
#include<math.h>
using namespace std;

int main()
{
	int A,B;
	cin >> A >> B;
	if (A%2 == 0 || B % 2 == 0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main()
{
	int N,M,X,Y;
	cin >> N >> M >> X >> Y;
	int x[N+1], y[M+1];
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	x[N] = X;
	sort(x, x + N + 1);

	for (int i = 0; i < M; i++) {
		cin >> y[i];
	}
	y[M] = Y;
	sort(y, y + M + 1);

	if (y[0] - x[N] >= 1) {
		cout << "No War" << endl;
	}
	else {
		cout << "War" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	string s; cin >> s;
	string ss[] = {
		"dreameraser",
		"dreamerase",
		"dreamer",
		"eraser",
		"dream",
		"erase"
	};
	ll idx = 0;
	while(true) {
	JUMP:
		if (idx == s.size()) break;
		REP(j, 6) {
			if (s.substr(idx, ss[j].size()) == ss[j]) {
				idx += ss[j].size();
				goto JUMP;
			}
		}
		cout << "NO" << endl;
		return 0;
	}
	cout << "YES" << endl;

	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define fastio std::ios_base::sync_with_stdio(false), std::cout.tie(0), std::cin.tie(0);
#define N 100007
#define mxx INT_MAX

typedef long long ll;

std::set<std::string>st;
int main(){
	int num;
	std::string name;
	std::cin>>num;
	for(int x=0;x<num;x++){
		std::cin>>name;
		st.insert(name);
	}
std::cout<<st.size();


}

Measured memory_bytes: 19168
import random
import math
import copy

def calc(D, solution):
    satisfaction = 0
    for i in range(D):
        satisfaction = S[i][solution[i]-1] + satisfaction - \
                       sum([C[k] * ((i + 1) - last[k]) for k in range(26)]) \
                       + C[solution[i]-1] * ((i + 1) - last[solution[i]-1])

    return satisfaction


D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(D)]
satisfaction = 0
last = [0]*26
solution = []
# solution初期解
for i in range(D):
    best_sat = -100000000000
    for t in range(26):
        t_sat = S[i][t] + satisfaction - \
                sum([C[k]*((i+1)-last[k]) for k in range(26)]) + C[t]*((i+1)-last[t])
        # print(str(t)+'t:'+str(t_sat)+', b:'+str(best_sat))
        if t_sat > best_sat:
            best_T = t
            best_sat = t_sat

    satisfaction = best_sat
    last[best_T] = i + 1
    solution.append(best_T+1)

for i in range(100):
    r = math.ceil(random.random()*26)
    if r == 0:
        r = 1
    f = math.floor(random.random()*D)
    f_solution = copy.deepcopy(solution)
    f_solution[f] = r
    present_sat = calc(D,solution)
    new_sat = calc(D,f_solution)
    # print(present_sat,new_sat)
    if new_sat > present_sat:
        solution = f_solution

    # print(present_sat)

for i in range(D):
    print(solution[i])

# print(satisfaction)


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

int n;

void dfs(string s, char mx) {
    if (s.size() == n) {
        cout << s << endl;
    } else {
        for (char c = 'a'; c <= mx; c++) {
            dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx));
        }
    }
}

int main() {
    cin >> n;

    dfs("", 'a');

    return 0;
}


Measured memory_bytes: 1536
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    for (int i = 0; i < N; i++) {
      int a = sc.nextInt();
    }
    int ans = (N - 1) / (K - 1);
    if ((N - 1) % (K - 1) != 0) {
      ans += 1;
    }
    System.out.println(ans);
  }
}


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

using namespace std;

int main(){
	int N,temp,temp1;
	int A[1000];
	long double total,total1;

	scanf("%d",&N);
	for(temp=0;temp<N;temp++){
		cin >> A[temp];
	}
	for(temp=0,total=0;temp<N;temp++){
		total+=(1/(long double)A[temp]);
	}
	total1=1/total;
	cout << total1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int cnt;
void insertionSort(int *A,int n,int g){
  for(int i=g;i<n;i++){
    int v=A[i];
    int j=i-g;
    while(j>=0&&A[j]>v){
      A[j+g]=A[j];
      j-=g;
      cnt++;
    }
    A[j+g]=v;
  }
}
void shellSort(int *A,int n){
  cnt=0;
  int r=1;
  vector<int> G;
  while(r<=n){
    G.push_back(r);
    r*=2;
  }
  int m=G.size();
  reverse(G.begin(),G.end());
  cout<<m<<endl;
  for(int i=0;i<m;i++) cout<<G[i]<<" \n"[i==m-1];
  for(int i=0;i<m;i++) insertionSort(A,n,G[i]);
  cout<<cnt<<endl;
}
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  shellSort(A,n);
  for(int k=0;k<n;k++) cout<<A[k]<<endl;
  return 0;
}


Measured memory_bytes: 7060
//SAIKH SERAJ FAHIM, CSE-19-HSTU, BANGLADESH.

#include<iostream>
using namespace std;
int main()
{
    int n,k,i,count=0;
    cin>>n>>k;
    int ar[n];
    for(i=0; i<n; i++)
        cin>>ar[i];
    for(i=0; i<n; i++)
    {
        if(ar[i]>=k)
            count++;
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 640
# coding: utf-8


def can_match():
    s = input().rstrip()
    t = input().rstrip()
    if s == t:
        return True
    for i in range(1, len(s)):
        tmp = s[i:] + s[0:i]
        if tmp == t:
            return True
    return False


print("Yes" if can_match() else "No")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld double
long double PI =3.14159265;
using ll = long long;

const ll modo=1e9+7;
const ll ms=1e6+5;
const ll inf=-1e17;


ll ar[ms];
ll vv[3000][3];
int main()
{
    idfc;

    ll n,m;
    cin>>n>>m;

    ll i;
    ll j;
    ll a,b,c;
    for(i=1;i<=m;i++)
    {
        cin>>vv[i][0]>>vv[i][1]>>vv[i][2];
    }

    for(i=1;i<=n;i++)
    {
        ar[i]=inf;
    }
    ar[1]=0;

    for(i=1;i<n;i++)
    {
        for(j=1;j<=m;j++)
        {
            a=vv[j][0];
            b=vv[j][1];
            c=vv[j][2];
            if((ar[a]!=inf)&&((ar[a]+c)>ar[b]))
            {
                ar[b]=ar[a]+c;
            }
        }
    }
    ll x=ar[n];

    for(i=1;i<n;i++)
    {
        for(j=1;j<=m;j++)
        {
            a=vv[j][0];
            b=vv[j][1];
            c=vv[j][2];
            if((ar[a]!=inf)&&((ar[a]+c)>ar[b]))
            {
                ar[b]=ar[a]+c;
            }
        }
    }
    if(ar[n]>x)
    {
        cout<<"inf";
        return 0;
    }
    cout<<ar[n];

    return 0;
}


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


int G[100][100];
int d[100]={0};
queue<int> que;
int distance_from0 = 1;

int main() {
    // 制約見て！！！デカかったらlong longにすること！
    int n, u, k, v;
    cin >> n;
    rep(i, n) {
        cin >> u >> k;
        u--;
        rep(j, k) {
            cin >> v;
            v--;
            G[u][v] = 1;
        }
    }
    que.push(0);
    d[0]=0;
    while(que.size()>0){
        int s = que.front();
        que.pop();
        rep(i,n){
            if(i>0 && d[i]==0 && G[s][i]==1){
                que.push(i);
                d[i] = d[s]+1;
            }
        }
    }

    rep(i,n){
        if(i>0 && d[i]==0){
            d[i] = -1;
        }
    }
    rep(i,n){
        printf("%d %d\n",i+1,d[i]);
    }
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint fact(int n){
	static vector<mint> memo={1};
	if(memo.size()<=n){
		int k=memo.size();
		memo.resize(n+1);
		for(;k<=n;k++) memo[k]=memo[k-1]*k;
	}
	return memo[n];
}

mint fact_inverse(int n){
	static vector<mint> memo={1};
	if(memo.size()<=n){
		int k=memo.size();
		memo.resize(n+1);
		memo[n]=inverse(fact(n));
		for(int i=n;i>k;i--) memo[i-1]=memo[i]*i;
	}
	return memo[n];
}

mint choose(int n,int k,int type=0){
	if(k<0 || n<k) return 0;
	if(type==0){
		return fact(n)*fact_inverse(k)*fact_inverse(n-k);
	}
	else{
		if(k>n-k) k=n-k;
		mint res=fact_inverse(k);
		rep(i,k) res*=n-i;
		return res;
	}
}

mint f(int r,int c){ return choose(r+c+2,r+1)-1; }

int main(){
	int r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2;
	cout<<f(r2,c2)-f(r1-1,c2)-f(r2,c1-1)+f(r1-1,c1-1)<<'\n';
	return 0;
}


Measured memory_bytes: 22392
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream> // cout, endl, cin
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;

int main(){
    int x;
    cin >> x;
    if(x == 1) cout << 0 << endl;
    if(x == 0) cout << 1 << endl;
}

Measured memory_bytes: 3628
use std::io;

fn main() {
    let r = input();

    let area = r * r * std::f64::consts::PI;
    let circumference = 2.0 * r * std::f64::consts::PI;

    println!("{} {}", area, circumference);
}

fn input() -> f64 {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    
    s.trim().parse().unwrap()
}



Measured memory_bytes: 5060
h1, m1, h2, m2, k = [int(i) for i in input().split()]

m1 += h1 * 60
m2 += h2 * 60

m = 0
if m1 == m2:
  m = 24 * 60
elif m1 < m2:
  m = m2 - m1
else:
  m = 24 * 60 - (m1 - m2)

print(m - k)

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

int main(){
    int n, k, temp, price[1001]={0};
    cin>>n>>k;
    for (int i=0; i<n; i++){
        cin>>temp;
        price[temp]++;
    }
    
    int point = 0, sum = 0;
    for (int i=0; point<k; i++){
        while ((price[i]) && (point<k)){
            sum+=i;
            price[i]--;
            point++;
        }
    }
    cout<<sum<<endl;

    return 0;
}

Measured memory_bytes: 3568
const getMaxv = (n, arr) => {
  let j = 1;
  let maxv = -Infinity;
  let min = Infinity;
  for (j = 0; j < n; j++) {
    maxv = Math.max(maxv, arr[j] - min);
    min = Math.min(min, arr[j]);
  }
  console.log(maxv);
};

process.stdin.resume();
process.stdin.setEncoding("utf8");
let input_string = "";

process.stdin.on("data", chunk => {
  input_string += chunk;
});

process.stdin.on("end", () => {
  const lines = input_string.split("\n").filter(v => {
    return v !== "";
  });
  getMaxv(lines[0], lines.slice(1));
});



Measured memory_bytes: 49312
S = [s for s in input()]
#1文字目がA
if S[0] == "A":
    #3文字目〜末尾から2文字目の走査
    if "C" in S[2:-1]:
        S.remove("A")
        S.remove("C")
        S = "".join(S)
        if S.islower():
            print("AC")
        else:
            print("WA")
    else:
        print("WA")
else:
    print("WA")



Measured memory_bytes: 3064
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

ans = "Yes"
t = 0
for a, b in AB:
    t += a
    if t > b:
        ans = "No"
        break

print(ans)

Measured memory_bytes: 31804
def solve():
    n = int(input())
    h = list(map(int, input().split()))
    print(watering(h))


def watering(h):
    if 0 in h:
        x = h.index(0)
        return watering(h[:x]) + watering(h[x + 1:])
    if h:
        if max(h) == 1:
            return 1
        else:
            h = list(map(lambda x: x - 1, h))
            return watering(h) + 1
    return 0



if __name__ == '__main__':
    solve()


Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,y; cin>>n>>y;
  bool is_exist = false;
  y/=1000;
  for(int i=y/10; i>=0; --i){
    if( i > n || is_exist ) break;
    for(int j=(y-i*10)/5; j>=0; --j){
      if( i+j > n || is_exist ) break;
      if( (y- i*10 - j*5) + i + j == n){
        is_exist = true;
        cout << i << ' '<< j << ' ' << (y- i*10 - j*5) << endl; 
        break;
      }
    }
  }
  if (!is_exist) cout << "-1 -1 -1" << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Contest.B
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			var cin = new Scanner();

			string s = cin.Next();
			var a = new List<int>();
            for (int i = 0; i < 26; i++)
            {
				a.Add(0);

            }
            foreach (var item in s)
            {
				a[item - 'a']++;
            }
            if (a.Count(x => x % 2 == 1) == 0) Console.WriteLine("Yes");
            else Console.WriteLine("No");

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 13268
from itertools import combinations

n = int(input())
D = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for _ in range(n):
    s = input()[0]
    if s in D:
        D[s] += 1
print(sum([i * j * k for i, j, k in combinations(D.values(), 3)]))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9

int main(){
	int a,b;
	cin>>a>>b;
	cout<<(a*b%2?"Odd":"Even")<<endl;
	return 0;
}


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

namespace ABC083_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var NAB = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = NAB[0];
            var A = NAB[1];
            var B = NAB[2];

            var ts = 0;
            for (int i = 1; i <= N; i++)
            {
                var t = i;
                var s = 0;
                while (t >= 10)
                {
                    s += t % 10;
                    t /= 10;
                }
                s += t;
                ts += (A <= s && s <= B) ? i : 0;
            }
            Console.WriteLine(ts);
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;


int N;
vector<int> p;

bool solve() {
    for (int i = 0; i < N; ++i) {
        for (int j = i; j < N; ++j) {
            swap(p[i], p[j]);

            bool ok = true;
            for (int k = 0; k < N; ++k) if (p[k] != k) ok = false;
            if (ok) return true;

            swap(p[i], p[j]);
        }
    }
    return false;
}

int main() {
    while (cin >> N) {
        p.resize(N);
        for (int i = 0; i < N; ++i) cin >> p[i], --p[i];

        if (solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

int main(){
    string s;
    cin >> s;
    rep(i, s.size()){
        if(i == 4) cout << ' ';
        cout << s[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
int main() {
	int d;
	cin >> d;
	V p(26);
	V l(26, 0);
	VV up(d, V(26));
	ll now = 0;
	rep(i, 26) cin >> p[i];
	rep(i, d) rep(j, 26) cin >> up[i][j];
	rep(i, d) {
		int x;
		cin >> x;
		x--;
		l[x] = i + 1;
		now += up[i][x];
		rep(j, 26) {
			now -= p[j] * ((i + 1) - l[j]);
		}
		cout << now << endl;
	}
	return 0;
}

Measured memory_bytes: 3596
n = int(input())
A = [int(i) for i in input().split(" ")]
b = 0
B = [A[i] - (i+1) for i in range(n)]
B.sort()
b = B[n//2]
sc = 0

for i in range(n):
    sc += abs(A[i] - (b+i+1))
    #print(A[i] - (b+i+1))
print(sc)


Measured memory_bytes: 25156
A, B, C, D, E, F = map(int, input().split())
A *= 100
B *= 100

dp = [-1] * (F + 1)  # dp[f] = sugar
dp[0] = 0

for f in range(F + 1):
    if A + f <= F:
        dp[A + f] = max(dp[A + f], dp[f])
    if B + f <= F:
        dp[B + f] = max(dp[B + f], dp[f])
    if C + f <= F and dp[f] >= 0:
        water = f - dp[f]
        maxSugar = (water // 100) * E
        if dp[f] + C <= maxSugar:
            dp[C + f] = max(dp[C + f], dp[f] + C)
    if D + f <= F and dp[f] >= 0:
        water = f - dp[f]
        maxSugar = (water // 100) * E
        if dp[f] + D <= maxSugar:
            dp[D + f] = max(dp[D + f], dp[f] + D)

ans = (0, 0)
mx = -1
for f in range(1, F + 1):
    if mx < 100 * dp[f] / f:
        mx = 100 * dp[f] / f
        ans = (f, dp[f])
print(*ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>

using namespace std;

int N, T;
int h[100000];

int main() {
  while (cin >> N >> T) {
    for (int i = 0; i < N; ++i) {
      cin >> h[i];
    }
    long long first = 0;
    long long cycle = 1;
    for (int i = 0; i < N; ++i) {
      long long r;
      if (T < first) {
	r = 0;
      } else if (cycle > h[i]) {
	r = (T-first) / cycle;
	if ((T-first) % cycle >= h[i]) r++;
      } else {
	cycle = h[i];
	r = (T-first) / cycle;
      }
      first += h[i];
      cout << r+1 << endl;
    }
  }
}

Measured memory_bytes: 3508
#include <bits/stdc++.h>
#define LL long long
#define PB push_back
#define X first
#define Y second
#define INF 1000 * 1000 * 1000
using namespace std;
const LL mod = 1000 * 1000 * 1000 + 7;
const LL ob = (mod + 1) >> 1;
vector<pair<pair<int , int> , int> > edges;
vector<pair<int , int> > vert;
vector<vector<pair<int , int> > > g(500005);
int d[500005];
int relaxed[500005];
int getIdx(pair<int , int> u)
{
	return lower_bound(vert.begin() , vert.end() , u) - vert.begin();
}
int main()
{
	ios_base::sync_with_stdio(0);
	int N , M;
	cin >> N >> M;
	for(int i = 0; i < M; i++)
	{
		int u , v , c;
		cin >> u >> v >> c;
		edges.PB({{u , v} , c});
		vert.PB({u , c});
		vert.PB({v , c});
	}
	sort(vert.begin() , vert.end());
	vert.resize(unique(vert.begin() , vert.end()) - vert.begin());
	int n = vert.size();
	for(int i = 0; i < vert.size(); i++)
	{
		g[i].PB({vert.size() + vert[i].X , 0});
		g[vert.size() + vert[i].X].PB({i , 1});
	}
	for(int i = 0; i < M; i++)
	{
		pair<int , int> u = {edges[i].X.X , edges[i].Y} ,  v = {edges[i].X.Y , edges[i].Y};
		g[getIdx(u)].PB({getIdx(v) , 0});
		g[getIdx(v)].PB({getIdx(u) , 0});
	}
	for(int i = 0; i <= 500004; i++)
		d[i] = INF;
	int start = 1 + vert.size();
	d[start] = 0;
	deque<int> deq;
	deq.PB(start);
	while(!deq.empty())
	{
		int u = deq.front();
		deq.pop_front();
		if(relaxed[u])
		{
			continue;
		}
		relaxed[u] = 1;
		for(auto v : g[u])
		{
			int to = v.X , type = v.Y;
			if(!type)
			{
				if(d[to] > d[u])
				{
					d[to] = d[u];
					deq.push_front(to);
				}
			}
			else
			{
				if(d[to] == INF)
				{
					d[to] = d[u] + 1;
					deq.PB(to);
				}
			}
		}
	}
	if(d[vert.size() + N] == INF)
	{
		cout << -1 << endl;
		return 0;
	}
	cout << d[vert.size() + N];
}




Measured memory_bytes: 40704
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}



int main() {

  long n, m, k;
  cin >> n ;

  //4-5-6の無限ループでは？
  //5-6の無限ループ

  long ans = (n/11)*2;

  long modr = n%11;

  if (modr>0){
    ans++;
    if (modr>6)ans++;
  }

  cout <<ans <<endl;



}




















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

int main()
{
  int seg[] = {0x3f, 0x6, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x27, 0x7f, 0x6f};
  int n;

  while (scanf("%d", &n), n != -1){
    int ans = 0;
    while (n--){
      int m;
      scanf("%d", &m);
      cout << bitset<7>(ans ^ seg[m]) << '\n';
      ans = seg[m];
    }
  }

  return (0);
}

Measured memory_bytes: 1212
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	m := map[string]int{}
	for i := 0; i < n; i++ {
		var tmp string
		fmt.Scan(&tmp)
		_, exists := m[tmp]
		if exists {
			fmt.Println("NO")
			return
		} else {
			m[tmp] = 1
		}
	}

	fmt.Println("YES")
}


Measured memory_bytes: 19840
#include<stdio.h>

int main(void) {
    int K, X;
    scanf("%d %d", &K, &X);
    for(int i = X - (K - 1); i < (X + K); i++){
        printf((i == X - (K - 1)) ? "%d" : " %d", i);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 128
sx,sy,tx,ty = map(int,input().rstrip().split(" "))
dx = tx - sx
dy = ty-sy
ans = ""
ans += "R"*dx + "U" * dy
ans += "L" * dx + "D" * dy
ans += "D" + "R" * (dx + 1) + "U" * (dy + 1) + "L"
ans += "U" + "L" * (dx + 1) + "D" * (dy + 1) + "R"
print(ans)

Measured memory_bytes: 9100
#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdio>//C的输入输出
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <limits.h>
#include <bitset>//bitset可按位定义串
//比如：bitset <1000> all;定义一个1000位的串
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
#include <numeric>//常用数字操作 一般和algorithm搭配使用
#include <functional>//STL定义运算函数（代替运算符）
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define LOCAL
#define zeros(a,n) memset(a,0,(n)*sizeof(a[0]))
const int modn = 1e9+7;
int mod(int x) { return x<0?x+modn:x<modn?x:x-modn; }
const int N = 200005;
int a[N];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int k, n;
    cin>>k>>n;
    for(int i = 0; i<n;++i) cin>>a[i];
    int ans = INT_MAX;
    for(int i=0; i<n;++i){
        if(i == n-1) ans = min(ans, (a[i]-a[0]+k)%k);
        else ans=min(ans,(a[i]-a[i+1]+k)%k);
    }
    cout<<ans<<"\n";
    return 0;
}



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

int main() {
  int N, M;
  cin >> N >> M;
  vector<string> L(N);

  for(int i = 0; i < N; i++){
    string S;
    cin >> S;
    L.at(i) = S;
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      if(L.at(i).at(j) == '#'){/*direction 5*/
        cout << '#';
      }
      else{
        int counter = 0;
        if(j > 0){
          if(L.at(i).at(j-1) == '#'){/*direction 4*/
            counter++;
          }
        }
        if(j < M-1){
          if(L.at(i).at(j+1) == '#'){/*direction 5*/ 
            counter++;
          }
        }
        if(i > 0){
          if(L.at(i-1).at(j) == '#'){/*direction 8*/
            counter++;
          }
          if(j > 0){
            if(L.at(i-1).at(j-1) == '#'){/*direction 7*/
              counter++;
            }
          }
          if(j < M-1){
            if(L.at(i-1).at(j+1) == '#'){/*direction 9*/
              counter++;
            }
          }
        }
        if(i < N-1){
          if(L.at(i+1).at(j) == '#'){/*direction 2*/
            counter++;
          }
          if(j > 0){
            if(L.at(i+1).at(j-1) == '#'){/*direction 1*/
              counter++;
            }
          }
          if(j < M-1){
            if(L.at(i+1).at(j+1) == '#'){/*direction 3*/
              counter++;
            }
          }
        }
        cout << counter;
      }
    }
    cout << '\n';
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lli n;
    cin>>n;
    lli a[n],i;
    for(i=0;i<n;i++)
    cin>>a[i];
    for(i=0;i<n;i++)
    {
        if(a[i]%2==0 && a[i]%3!=0 && a[i]%5!=0)
        {
             cout<<"DENIED"<<"\n";
             return 0;
        }
    }
     cout<<"APPROVED"<<"\n";
}
    

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

const long long INF = 1LL << 60;

int main() {
  long long N,M,x,res;
  cin >> N >> M;
  long long A[100100];

  std::priority_queue<long long> Q;
  
  rep(i,N){
    cin >> A[i];
    Q.push(A[i]);
  }
  
  while(M){
    x=Q.top()/2;
    Q.push(x);
    Q.pop();
    M--;
  }
  
  while(!Q.empty()){
    res += Q.top();
    Q.pop();
  }
  
  cout << res << endl;
  
}

Measured memory_bytes: 1912
#include <iostream>
#include <vector>

using namespace std;

template <typename T>
int BubbleSort(vector<T> &a) {
  int swap_times = 0;
  int n = a.size();
  bool has_sorted = false;
  while (!has_sorted) {
    has_sorted = true;
    for (int i = n - 1; i >= 1; --i) {
      if (a[i-1] > a[i]) {
        swap(a[i], a[i-1]);
        ++swap_times;
        has_sorted = false;
      }
    }
  }
  return swap_times;
}

template <typename T>
void PrintVector(vector<T> &a) {
  int n = a.size();
  if (n <= 0) return;
  cout << a[0];
  for (int i = 1; i < n; ++i) {
    cout << ' ' << a[i];
  }
  cout << endl;
  return;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int res = BubbleSort<int>(a);
  PrintVector<int>(a);
  cout << res << endl;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,T;
  cin>>N>>T;
  
  vector<int>t(N);
  vector<int>c(N);
  
 
  int min=1000;
  
  int sum=0;
  
  
  for(int i=0;i<N;i++){
    cin>>c.at(i)>>t.at(i);
    
    if(t.at(i)<=T&&c.at(i)<=min){
      min=c.at(i);
      sum++;
  }
  }
  
  if(sum==0){
    cout<<"TLE"<<endl;
  }
  else{
    
  
  
      cout<<min<<endl;
  }
  
}

  
  

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int testcase_ends() {
  intmax_t d;
  scanf("%jd", &d);
  if (d == 0) return 1;
  size_t n;
  size_t m;
  scanf("%zu %zu", &n, &m);

  std::vector<intmax_t> S(n+1);
  for (size_t i=1; i<n; ++i) {
    scanf("%jd", &S[i]);
  }
  S[n] = d;
  std::sort(S.begin(), S.end());

  intmax_t res = 0;
  for (size_t i=0; i<m; ++i) {
    intmax_t k;
    scanf("%jd", &k);

    auto it = std::lower_bound(S.begin(), S.end(), k);
    // fprintf(stderr, "%td: %jd\n", it-S.begin(), *it);

    intmax_t cur = abs(*it-k);
    if (it != S.begin())
      cur = std::min<intmax_t>(cur, std::abs(k-*--it));

    // fprintf(stderr, "%jd\n", cur);
    res += cur;
  }
  printf("%jd\n", res);
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 3200
function main()
    txt = readlines()
    S = split(txt[1], "")
    T = split(txt[2], "")

    max_resem = 0
    for i in 1:(length(S) - length(T) +  1)
        resem = 0
        for j in 1:length(T)
            if S[i + j - 1] == T[j]
                resem += 1
            end
        end

        if resem > max_resem
            max_resem = resem
        end

    end
    println(length(T) - max_resem)
end

main()

Measured memory_bytes: 168608
/*author : Yashvardhan
Wednesday, April 29, 2020
11:50 PM
*/

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

using ll = long long;

#define int ll
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define vpi vector<pi>
#define ff first
#define ss second
#define mp make_pair
#define endl '\n'
#define all(a) a.begin(), a.end()
#define initialise(a, x) memset(a, x, sizeof(a))
#define rev(Y) reverse(all(Y))

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#ifdef __APPLE__
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << "  ";
	__f(comma + 1, args...);}
#else
#define debug(...)
#endif

template <typename T> ostream& operator << (ostream& os,const vector<T>& v){for(int i=0;i<v.size();++i) os<<v[i]<<" ";return os;} 
template <typename T> ostream& operator << (ostream& os,const set<T>& v){for(auto it:v) os<<it<<" ";return os;} 
template <typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {os<<v.ff<<" "<<v.ss;return os;}

const int mod = 2019;
const int inf = 2e18;
const int ninf = -2e18;

int takemod(int a){return ((a%mod)+mod)%mod;}

int pow(int a, int b, int m)
{
	int ans = 1;
	a %= m;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int a){return takemod( pow( takemod(a), mod-2,mod ) );}


signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	#ifdef __APPLE__
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("error.txt","w",stderr);
	#endif

	time_t t1, t2;
	t1 = clock();
	
	string tmp;
	cin >> tmp;
	rev(tmp);

	int n = tmp.size();
	string s = "*" + tmp;

	int pref[n + 1];
	pref[0] = 0;
	int tomul = 1;
	map<int,int> counti;
	counti[0] = 1;
	for(int i = 1; i <= n; i++){
		pref[i] = (pref[i - 1] + (tomul * (s[i] - '0')) % mod) % mod;
		tomul = (tomul * 10) % mod;
		counti[pref[i]]++;
	}

	int ans = 0;
	for(int i = n; i >= 1; i--){
		counti[pref[i]]--;
		ans += counti[pref[i]];
	}

	cout << ans << endl;	

	t2 = clock();
	cerr << endl << t2-t1 << endl;
	
	return 0;
}



Measured memory_bytes: 5360
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include <sstream>
#include<map>
#include<cmath>
#include<queue>
#include <functional>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define PI 3.141592

using namespace std;

int main() {
	int a;
	cin >> a;

	string S;
	cin >> S;

	if (a < 3200)
	{
		printf("red");
	}
	else
	{
		cout << S;
	}

	//printf("%.10f", result);
}


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

int main() {
  int K , A , B ;
  cin >> K >> A >> B ;
  if (B/K-A/K>0){
    cout << "OK" << endl;
  }
  else if (B/K-A/K==0&&A%K==0){
    cout << "OK" << endl;
  }
  else {
    cout << "NG" << endl;
  }
}



Measured memory_bytes: 3636
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        
        if((c-a-b)*(c-a-b)>4*a*b && c-a-b > 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35688
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct PrimeTable{
	vector<int> primeList;
	vector<bool> isPrime;
	PrimeTable(int n) : isPrime(n + 1,true){
		isPrime[0] = false;
		isPrime[1] = false;
		for(int i = 4;i <= n;i += 2) isPrime[i] = false;
		for(int i = 3;i * i <= n;i += 2){
			if(!isPrime[i]) continue;
			for(int j = i * 2;j <= n;j += i) isPrime[j] = false;
		}
		for(int i = 0;i <= n;i++){
			if(isPrime[i]) primeList.push_back(i);
		}
	}
};

signed main(){
	int x;
	PrimeTable pt(200000);
	cin >> x;
	for(int i = x;;i++){
		if(pt.isPrime[i]){
			cout << i << endl;
			return 0;
		}
	}
}

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

int main() {
  ll n,m,ans=0,b,c,indn=0,indm=0;
  cin >> n >> m;
  vector<ll>a(n);
  vector<pair<ll,ll>>cb;
  rep(i,n) cin >> a.at(i);
  rep(i,m) {
  	cin >> b >> c;
  	cb.push_back(make_pair(c,b));
  }
  sort(a.begin(),a.end());
  sort(cb.begin(),cb.end());
  reverse(cb.begin(),cb.end());
  while(indn<n && indm<m){
  	ll i=0;
  	while(i<cb.at(indm).second && indn<n){
  		ll flg=0;
  	    while(flg==0 && indn<n){
  	    	if(a.at(indn)<cb.at(indm).first) a.at(indn)=cb.at(indm).first;
  	    	i++;
  	    	flg=1;
  		}
  		indn++;
  	}
  	indm++;
  }
  rep(i,n) ans+=a.at(i);
  cout << ans <<endl;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define fort(i,n) for (int i = 1; i <= n; ++i)
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define sz size()
#define er erase
#define fr first
#define sc second
#define rc(x) return cout << x, 0
using namespace std;

int n,h[100005],dp[100005];

int32_t main()
{
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    fort (i,n)
        cin >> h[i];
    dp[2]=abs(h[1]-h[2]);
    for (int i = 3; i <= n; ++i)
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    cout << dp[n];
}


Measured memory_bytes: 1024
from sys import stdin

H, N = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
AB.sort(reverse=True, key=lambda x: x[0])
dp = [[10 ** 9] * (N + 1) for _ in range(H + AB[0][0] + 1)]

for k in range(N + 1):
    dp[0][k] = 0

for i in range(len(dp)):
    for j in range(N):
        cnt = 0

        if i - AB[j][0] >= 0:
            dp[i][j + 1] = min(dp[i - AB[j][0]][j + 1] + AB[j][1], dp[i][j])
        else:
            dp[i][j + 1] = dp[i][j]

ans = 10 ** 9

for i in range(H, len(dp)):
    for j in range(N + 1):
        ans = min(ans, dp[i][j])

print(ans)

Measured memory_bytes: 129244
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main() {
  lint n, k, s = 0;
  cin >> n >> k;
  if(k % 2 == 0){
    s += (lint)pow(n/k, 3);
    s += (lint)pow((n+k/2)/k, 3);
  }
  else s += (lint)pow(n/k, 3);
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>
#include <functional>

using namespace std;
#define ALL(x)              (x).begin(),(x).end()
typedef long long           ll;
#define REP(i, n)           for (ll i = 0 ; i < (ll)n ; ++i)
#define REPN(i, m, n)       for (ll i = m ; i < (ll)n ; ++i)
#define INF                 (ll)1e9
#define MOD                 (1000 * 1000 * 1000 + 7)
#define Ceil(x, n)          (((((x))+((n)-1))/n))
#define CeilN(x, n)         (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)        ((x)-(x)%(n))
#define IsOdd(x)            (((x)&0x01UL) == 0x01UL)
#define IsEven(x)           (!IsOdd((x)))
#define M_PI                3.14159265358979323846
typedef pair<ll, ll>	    P;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
struct MyCin {
	void operator()(P &a) {
		cin >> a.first >> a.second;		
	}
};

int main()
{
	ll N;
	cin >> N;
	vector<pair<ll, ll>> A(N);
	for_each(ALL(A), MyCin());
	reverse(ALL(A));

	ll addSum = 0;
	for (auto one : A) {
		ll addAll = one.first + addSum;
		ll addOne = CeilN(addAll, one.second) - addAll;
		addSum += addOne;
	}

	cout << addSum << endl;
	return 0;
}


Measured memory_bytes: 1792