akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    rep(i, 3) {
        if (S[i] == '1') cout << '9';
        else cout << '1';
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int, input().split()))

counter = 0
ans = 0
for i in range(N-1):
    if H[i] >= H[i+1]:
        counter += 1
    else:
        ans = max(ans,counter)
        counter = 0
ans = max(ans,counter)
print(ans)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
using namespace std;
using ll = unsigned long long;
using p = pair<int, int>;

int main()
{
    int x, n;
    cin >> x >> n;

    auto p = vector<int>(n);

    rep(i, 0, n)
    {
        cin >> p[i];
    }

    int ans = x;
    int t = x;
    int a = 0;
    while (true)
    {
        auto result = std::find(p.begin(), p.end(), t);
        // pにない
        if (result == p.end())
        {
            int ab = abs(x - t);
            ans = t;
            a = ab;
            break;
        }
        t++;
    }

    t = x;
    while (true)
    {
        auto result = std::find(p.begin(), p.end(), t);
        // pにない
        if (result == p.end())
        {
            int ab = abs(x - t);
            if (ab <= a)
            {
                if (ans > t)
                {
                    ans = t;
                }
            }

            break;
        }
        t--;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
char a[1000];
int m,k;
int main()
{
    cin>>m;
    scanf("%s",a);
    k=strlen(a);
    if(k>m)
    {
        for(int i=0;i<m;i++)
        {
            cout<<a[i];
        }
        cout<<"..."<<endl;
    }
    else
        cout<<a<<endl;
}


Measured memory_bytes: 3680
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int matrix[305][305];
int N;
typedef long long ll;

bool valid(int a, int b) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (matrix[(i + a) % N][(j + b) % N] !=
				matrix[(j + a) % N][(i + b) % N])
				return false;
		}
	}
	return true;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char ch;
			cin >> ch;
			matrix[i][j] = ch - 'a';
		}
	}
	ll ans = 0;
	
	for (int b = 0; b < N; b++) {
		if (valid(0, b)) {
			ans++;
		}
	}
	
	cout << ans * N << endl;
}

Measured memory_bytes: 640
import java.math.BigDecimal

fun main(args: Array<String>) {
    abc089c()
}

fun abc089c() {
    val n = readLine()!!.toInt()
    val initials = (1..n).map { readLine()!![0] }

    val march = arrayOf('M', 'A', 'R', 'C', 'H')

    val marchCounts = march.map { m ->
        BigDecimal(initials.count { it == m })
    }

    val patterns = (0..4).map { i ->
        (i + 1..4).map { j ->
            (j + 1..4).map { k ->
                marchCounts[i] * marchCounts[j] * marchCounts[k]
            }
        }.flatten()
    }.flatten()

    val answer = patterns.fold(BigDecimal.ZERO, BigDecimal::add)

    println(answer)
}


Measured memory_bytes: 38012
from sys import stdin

def main():
    N = int(input())
    A, B = map(int, input().split())
    P = map(int, input().split())

    q1, q2, q3 = 0, 0, 0
    for n in P:
        if n <= A:
            q1 += 1
        elif A < n <= B:
            q2 += 1
        else:
            q3 += 1
    print(min(q1, q2, q3))

input = lambda: stdin.readline()
main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 

#define MAX 1000005
/*
#define mod 1000000007

ll add(ll a,ll b)
{
	return (mod+(a+b)%mod)%mod;
}
ll mul(ll a,ll b)
{
	return (mod+(a*b)%mod)%mod;
}
*/

// a*x + b = a2*x + b2
// (b2 - b )/(a-a2) 

struct Line {
	ll a, b;
	ll value(ll x)
	{
		return a*x + b;
	}
	
	pair<ll,ll> intersect(Line he)
	{
		ll one = he.b - b;
		ll two = a - he.a;
		if(two < 0)
		{
			two = two * -1;
			one = one *-1;
		}
		return {one, two};
	}
	
};
unordered_map <ll, vector <ll>> mp;

int main()
{
	
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	  
  	ll n;
	cin>>n;
	
	ll c;
	cin>>c;
  
	ll h[n];
	for(ll i=0;i<n;i++){
		cin>>h[i];
	}
	
	ll dp[n];
	
	vector <Line> lines;
	
	ll start = 0;
  
	for(ll i=0;i<n;i++)
	{
		while(start < ((ll)lines.size()-1))
		{
			Line A = lines[start];
			Line B = lines[start+1];
			if(A.value(h[i]) >= B.value(h[i]))
				start++;
			else
				break;
		}
		dp[i] = 0;
		if(i!=0)
		{
			dp[i] = lines[start].value(h[i]) + (h[i]*h[i]) + c;
		}
		Line line = {-2*h[i], dp[i] + h[i]*h[i]};
		while(start < (ll)lines.size()-1)
		{
			Line A = lines.end()[-1];
			Line B = lines.end()[-2];
			pair<ll,ll> prev = A.intersect(B);
			pair<ll,ll> nev = B.intersect(line);
			if(prev.first * nev.second >= nev.first * prev.second){
				lines.pop_back();
			}
			else
				break;
		}
		lines.push_back(line);
		
	}

	cout<<dp[n-1]<<endl;



}


Measured memory_bytes: 10368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <map>
#include <set>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    if(n+m==15){
        cout << '+' << endl;
    }
    else if(n*m==15){
        cout << '*' << endl;
    }
    else cout << 'x' << endl;



    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int main(int argc, char const *argv[]) {
  int N,M,K;
  ll calc;
  scanf("%d%d%d",&N,&M,&K);
  if(K>N*M){
    printf("No\n");
    return 0;
  }else if(K%N==0 || K%M==0){
    printf("Yes\n");
    return 0;
  }
  for (size_t i = 0; i < N; i++) {
    for (size_t j = 0; j < M; j++) {
      calc=M*i+N*j-(i*j*2);
      if(calc==K){
        printf("Yes\n");
        return 0;
      }
    }
  }
  printf("No\n");
  return 0;
}


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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

ll cnt = 0;
int n,k;

int main(){
  cin >> n >> k;
  cout << (n-1)/(k-1)+((n-1)%(k-1)>0) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin>>s>>t;
  int minx=10000;
  for(int i=0;i<s.size()-t.size()+1;i++){
    int x=0;
    for (int j=0;j<t.size();j++){
      if(t.at(j)!=s.at(i+j)){
        x+=1;
      }
    }
   minx=min(minx,x);
  }
  cout<<minx<<endl;
}
  
  


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
int x[100];
int main()
{
    long long  n,d,c=0;
    long long v;
    cin>>n>>d;
    long long x[n][d];

    for(int i=0;i<n;i++)
        for(int j=0;j<d;j++)
            cin>>x[i][j];


    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            v=0;
            for(int k=0;k<d;k++)
            v+=(x[i][k]-x[j][k]) * (x[i][k]-x[j][k]);

            long long r=sqrt(v);

            if(r*r==v)c++;
        }
    }

    cout<<c<<endl;


    return 0;
}


Measured memory_bytes: 384
import java.util.*;

public class Main{

    static int mod = (int) 1e9 + 7;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    static int INF = Integer.MAX_VALUE/2;

    public static void main(String args[]){

        Scanner scan = new Scanner(System.in);

        //Queue<int[]> q = new ArrayDeque<int[]>();
        String s = scan.next();
        String t = scan.next();
        Integer a = new Integer(scan.nextInt());
        Integer b = new Integer(scan.nextInt());
        String u = scan.next();
        
        if(u.equals(s)){
            System.out.println((a-1) + " " + b);
        }else{
            System.out.println(a + " " + (b-1));
        }

    }

    static int factorial(int n){
        if(n == 0){
          return 1;
        }
        return n * factorial(n-1);
    }


}

Measured memory_bytes: 21204
#標準入力
A,B,M = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
m = [list(map(int,input().split())) for i in range(M)]
n = list()
#割引券なしの最小値
min_a = min(a)
min_b = min(b)
sa = min_a + min_b
n.append(sa)
#割引券使用時の最小値
for i in range(M):
    su = a[m[i][0]-1] + b[m[i][1]-1] - m[i][2]
    n.append(su)

#比較＆出力
ans = min(n)
print(ans)

Measured memory_bytes: 42412
// AOJ 2592: Flowers
// 2017.11.30 bal4u@uu

#include <stdio.h>

int vw[100002], pf[100002], vf[100002], th[100002];
int n, pw;

double calc(double x)
{
	int i;
	double t, ans = pw * x;
	
	for (i = 0; i < n; i++) {
		t = th[i] - x * vw[i];
		if (t > 0) ans += t / (double)vf[i] * pf[i];
	}
	return ans;
}

int main()
{
	int i;
	double l, r, lm, rm, x, y, t, ans;

	while (scanf("%d", &n) && n > 0) {
		scanf("%d", &pw);
		for (i = 0; i < n; i++) scanf("%d%d%d%d", vw+i, pf+i, vf+i, th+i);

		l = 0, r = 1000;
		ans = 1e10;
		for (i = 0; i < 200; i++) {
			lm = (l * 2 + r) / 3;
			rm = (l + r * 2) / 3;
			x = calc(lm);
			y = calc(rm);
			if (x < y) r = rm;
			else       l = lm;
			t = x; if (y < t) t = y;
			if (ans > t) ans = t;
		}
		printf("%.8lf\n", ans);
	}
	return 0;
}

Measured memory_bytes: 3304
def main():
    k = int(input())
    lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 0
    
    while(len(lun) < k):
        target = lun[cnt]
        mod = target % 10
        if mod != 0:
            lun.append(target*10 + mod - 1)
            
        lun.append(target*10 + mod)
        
        if mod != 9:
            lun.append(target*10 + mod + 1)
        cnt += 1
        
    print(lun[k-1])
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 7140
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  string s;
  cin >> s;
  int first_A_index, last_z_index;
  rep(i, s.size())
  {
    if (s[i] == 'A')
    {
      first_A_index = i;
      break;
    }
  }
  rep(i, s.size())
  {
    if (s[s.size() - 1 - i] == 'Z')
    {
      last_z_index = s.size() - 1 - i;
      break;
    }
  }

  int ans = last_z_index - first_A_index + 1;

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

Measured memory_bytes: 640
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    a, b, c, d = map(int,input().split())
    takahashi = (c - 1) // b
    aoki = (a - 1) // d
    print("Yes" if takahashi <= aoki else "No")
resolve()

Measured memory_bytes: 61656
#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
#define MAX_N 44

class Fib{
private:
  int size;
  int *A;
public:
  Fib(int size){
    this->size = size;
    makeFib();
  }

  int getFib(int n){
    return A[n];
  }

  void makeFib(){
    int i;
    this->A = (int*)malloc(sizeof(int)*(this->size+1));
    this->A[0] = 1;
    this->A[1] = 1;
    for(i = 2;i <= this->size;i++){
      this->A[i] = this->A[i-2]+this->A[i-1];
    }
  }

  ~Fib(){
    free(A);
  }
};
 
int main(){
 
    int n;
    Fib *fib = new Fib(MAX_N); 

    cin >> n;
 
    cout << fib->getFib(n) << endl;
 
    delete fib;

    return 0;
}

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

using namespace std;

int main(void){
    int n;
    cin >> n;
    
    string s, t;
    cin >> s >> t;
    
    string ans = "";
    for (int i = 0; i < n; i++){
        ans += s[i];
        ans += t[i];
    }
    
    cout << ans << endl;
}


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

typedef long long int  lli;
typedef unsigned long long int ulli;
typedef long double ldb;

#define pb push_back
#define popb pop_back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define forz(i,n) for( int i=0;i<n;i++)
#define forl(i, n) for(int i = 1; i<= n; i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)

using namespace std;


int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w" , stdout);
// #endif
	lli n, m, sum = 0, count = 0;
	cin >> n >> m;
	std::vector<int> v(n);
	forz(i, n)
	{
		cin >> v[i];
		sum += v[i];
	}
	sort(v.begin(), v.end(), greater<int>());

	forz(i, n)
	{
		if (sum % (m * 4))
		{
			if (v[i] > (sum / (4 * m)))
			{
				count++;
			}
		}
		else if (v[i] >= (sum / (4 * m)))
		{
			count++;
		}

	}
	if (count >= m)
	{
		cout << "Yes" << endl;
		// cout << count;
	}
	else
		cout << "No" << endl;
	return 0;
}




Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a, b, c, n, i;
	
	while(scanf("%d",&n) != EOF){
	
		for(i = 0;i < n;i++){
			scanf("%d %d %d", &a, &b, &c);
			
			if(a * a == b * b + c * c){
				printf("YES\n");
			}
			else if(b * b == a * a + c * c){
				printf("YES\n");
			}
			else if(c * c == a * a + b * b){
				printf("YES\n");
			}
			else{
				printf("NO\n");
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 580
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
A.reverse()
sumA=[0,]+list(accumulate(A))
mod=10**9+7
ans=0
for a, s in zip(A, sumA):
    ans+=((a%mod)*(s%mod))%mod
    ans%=mod
print(ans)

Measured memory_bytes: 31196
#include <cstdio>
#include <cctype>
#include <utility>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;while(isspace(c)){c=gcu();}if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m?-n:n;}
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(bool b) {pcu('0'+b);}
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

int main() {
	int n = in(), c = 0;
	for (int x : {25, 10, 5, 1})
		c += n / x, n %= x;
	outl(c);
}


Measured memory_bytes: 2620
def C(n, m)
	res = 1
	n.downto(n - m + 1) {|i| res *= i}
	1.upto(m) {|i| res /= i}
	return res
end

n, q = gets.split.map &:to_i
a = gets.split.map &:to_i

odd = a.count{|i| i.odd?}
even = n - odd

ans = 2 ** even
if q == 1
	i = 1
	cnt = 0
	while i <= odd
		cnt += C(odd, i)
		i += 2
	end
	ans *= cnt
else
	i = 0
	cnt = 0
	while i <= odd
		cnt += C(odd, i)
		i += 2
	end
	ans *= cnt
end

puts ans

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
const int N = 15;
vector< pair< int,int > > A[N];
int main(){
    int n,ans = 0;
    cin >> n;
    rep(i,n){
        int a,x,y;
        cin >> a;
        rep(j,a){
            cin >> x >> y;
            x--,A[i].push_back({x,y});
        }
    }
    for(int i=1;i<(1<<n);i++){
        int ch = 0;
        for(int j=0;j<n;j++){
            if(!((1<<j)&i)) continue;
            for(auto &x:A[j]){
                int state = ((1<<x.first)&i)?1:0;
                ch |= state!= x.second;
            }
        }
        if(!ch) ans = max(ans,__builtin_popcount(i));
    }
    cout << ans << endl;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;

bool is_k(string s) {
  string s2 = s;
  reverse(s2.begin(), s2.end());

  return s == s2;
}

int main() {
  string str;
  cin >> str;

  ll n = str.length();

  string str2 = str.substr(0, (n - 1) / 2);
  string str3 = str.substr((n + 3) / 2 - 1);

  // cout << str << endl;
  // cout << str2 << endl;
  // cout << str3 << endl;

  if (is_k(str) && is_k(str2) && is_k(str3)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys

n = int(input())
l_list = list(map(int, input().split()))


longest_index = l_list.index(max(l_list))
other_sum = 0

for i in range(n):
    if i == longest_index:
        continue
    else:
        other_sum += l_list[i]

if l_list[longest_index] < other_sum:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
N,K,S = map(int,input().split())
ans = [S for i in range(K)]
res = S+1 if S!=10**9 else 1
ans2 = [res for i in range(N-K)]
ans = ans+ans2
for i in range(N-1):
    print(ans[i],end=" ")
print(ans[-1])

Measured memory_bytes: 5668
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main(){
   int n,m,c;
   cin>>n>>m>>c;
   int b[m];
   int ans=0;
   for(int i=0;i<m;i++){
       cin>>b[i];
   }
   for(int i=0;i<n;i++){
       int sum=c;
       for(int j=0;j<m;j++){
           int a;
           cin>>a;
           sum+=a*b[j];
       }
       if(sum>0) ans++;
   }
   cout<<ans<<endl;
   
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define all(x) (x).begin(),(x).end()

int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n) {
        string s;
        cin >> s;

        sort(all(s));
        mp[s]++;
    }
    long long ans = 0;
    for (auto &p: mp) {
        int s = p.second;
        ans += (long long) s * (s - 1) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 11136
import queue

q = queue.Queue()

k = int(input())

for i in range(1,10):
    q.put(i)
    
while(k > 0):
    x = q.get()
    if x % 10 != 0:
        q.put(x*10 + (x%10 - 1))
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + (x%10 + 1))
    k -= 1
    
print(x)

Measured memory_bytes: 57428
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>

using namespace std;
using ll = long long int;

int main()
{
  int n, k;
  cin >> n >> k;
  int temp = 0;
  if(n % 2 == 0)
  {
    temp = n / 2;
  }else{
    temp = (n / 2) + 1;
  }
  if(temp >= k)
  {
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    ll A = 0, B = 0;
    rep(i,n) {
        if(a[i] > b[i]) A+=a[i]-b[i];
        if(b[i] > a[i]) B+=(b[i]-a[i])/2;
    }
    if(A <= B) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
  int n,c;
  cin>>n>>c;
  vector<vector<pair<int,int>>> v(c);

  rep(i,n){
    int s,t,x;
    cin>>s>>t>>x;
    s--;t--;
    x--;
    v[x].pb(mp(s,t));
  }

  vector<pair<int,int>> nv;
  rep(i,c){
    sort(all(v[i]));
    int m = v[i].size();
    rep(j, m){
      int d = 0;
      while(j+d+1 < m && v[i][j+d].se == v[i][j+d+1].fi) d++;
      nv.pb(mp(v[i][j].fi, v[i][j+d].se));
      j += d;
    }
  }

  sort(all(nv));

  int ans = 0;
  int crnt = 0;
  vector<int> ed(100005, 0);
  int iv = 0;
  rep(i,100004){
    while(iv < nv.size() && nv[iv].fi == i){
      crnt++;
      ans = max(ans, crnt);
      ed[nv[iv].se]++;
      iv++;
    }
    crnt -= ed[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2676
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int mod = 1e9 + 7;
int main()
{
	SPEED
	int n;
	cin >> n;
	map<string, int> mp;
	int count = -1;
	for (int i = 0; i < n; ++i)
	{
		string s;
		cin >> s;
		if (mp.count(s))
		{
			mp[s]++;
			count = max(mp[s], count);
		}
		else
		{
			mp[s] = 1;
			count = max(mp[s], count);
		}
	}
	map<string, int>::iterator itr;

	for (itr = mp.begin(); itr != mp.end(); ++itr) 
	{ 
		int temp = itr->second;
		if (temp == count)
		{
			cout << itr->first << '\n';
		}
    } 

	return 0;
}

Measured memory_bytes: 23808
n = int(input())
s = str(input())

count = [0] * 3

for i in range(n):
    if s[i] == 'R':
        count[0] += 1
    if s[i] == 'G':
        count[1] += 1
    if s[i] == 'B':
        count[2] += 1

ans = count[0] * count[1] * count[2]

for i in range(n):
    k = 1
    while i + 2 * k < n:
        l = []
        l.append(s[i])
        l.append(s[i+k])
        l.append(s[i+2*k])
        if l.count('R') == 1 and l.count('G') == 1 and l.count('B') == 1:
            ans -= 1
        
        k += 1

print(ans)

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

int main(){
	int a[10];
	for(int i = 0; i < 10; i++){
		cin >> a[i];
	}
	sort(a,a+10);
	cout << a[9] << endl;
	cout << a[8] << endl;
	cout << a[7] << endl;
}

Measured memory_bytes: 1176
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;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 stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=5005;
int n,mod,f[MAXN][MAXN],pre[MAXN];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int main()
{
	n=read();mod=read();f[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		int prod;
		if(n&1)
		{
			if(i<=(n+1)/2)prod=i-2+1;
			else prod=n-i+1+1;
		}
		else
		{
			if(i<=n/2+1)prod=i-2+1;
			else prod=n-i+1+1;
		}
		for(int j=0;j<prod;j++)pre[j]=f[i-1][j];
		for(int j=0;j<prod;j++)for(int k=1;j+prod*k<=n;k++)pre[j+prod*k]=(pre[j+prod*(k-1)]+f[i-1][j+prod*k])%mod;
		for(int j=0;j<=n;j++)f[i][j]=pre[j];
	}int ans=0;
	for(int i=0;i<n;i++)
		ad(ans,1LL*f[n][i]*(n-i)%mod);
	pr2(ans);
	return 0;
}


Measured memory_bytes: 97920
N,K=map(int,input().split())
A=[]
total=0
for i in range(N):
    C, B = map(int, input().split())
    A.append([C,B])

A.sort()

for i in range(N):
    total+=A[i][1]
    if total>=K:
        print(A[i][0])
        exit(0)

Measured memory_bytes: 20096
import heapq


n, m = [int(_) for _ in input().split()]
a_l = [(-1) * int(_) for _ in input().split()]

# print(a_l)

ans = 0
heapq.heapify(a_l)
for i in range(m):
    tmp = (-1) * heapq.heappop(a_l)
    heapq.heappush(a_l, (-1) * (tmp // 2))
    # print(a_l)
for i in range(len(a_l)):
    ans -= a_l[i]
print(ans)

Measured memory_bytes: 72344
#include<bits/stdc++.h>
int bo[101];
int main()
{
	using namespace std;
	int i,j,g,n;

	scanf("%d",&n);
	n*=2;
	for(i=0;i<n;i++){
		scanf("%d",&bo[i]);
	}
	sort(bo,bo+n,greater<int>());
	
	for(i=1;i<=n;i+=2){
		//printf("%d\n",bo[i]);
		g+=bo[i];
	}
	
	printf("%d\n",g);
	
	return 0;
}

Measured memory_bytes: 256
object Main {
    def main(args: Array[String]) {
        val price = scala.io.StdIn.readInt()
        var check = false

        for(i <- 0 to 25) {
            for(j <- 0 to 14) {
                if(4*i + 7*j == price) {check = true}
            }
        }

        if(check) println("Yes")
        else      println("No")
    }
}

Measured memory_bytes: 25548
import math

 

 
N,M = map(int,input().split())
S = input()
T = input()

pair = {N:S,M:T}


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    if gcd(n,m)==1:
        return lcd(n,m)
    global pair
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list = pair[n][::n_i]
    m_list = pair[m][::m_i]
#    print(c)
#    print(pair[m])
    if n_list[0:len(m_list)]==m_list:
        return lcd(n,m)
    else:
        return -1
n = max(pair.keys())
m = min(pair.keys())
if pair[N][0]!=pair[M][0]:
    print(-1)
elif N==M:
    if S==T:
        print(N)
    else:
        print(-1)
else:
    print(prove(n,m))



Measured memory_bytes: 3444
#include <stdio.h>

int main(void)
{
    int S, h, m, s;
    scanf("%d", &S);
    h = S / (60 * 60);
    m = (S - h * 60 * 60) / 60;
    s = S - h * 60 * 60 - m * 60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}



Measured memory_bytes: 2116
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner scanner;

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

	    long a=gl();
	    long b=gl();
       //System.out.print(min + " " + max);
//
        if (a>0) {
    	    System.out.print("Positive");
        }else if(b>=0){
        	 System.out.print("Zero");
        } else {
        	if((b-a)%2==0) {
        		System.out.print("Negative");
        	} else {
        		System.out.print("Positive");
        	}
        }
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35772
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    cout << (n-1)*(m-1);
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
 
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main(void){
   int N;
   cin >> N;
   if(N>=30){
       cout << "Yes" << endl;
   }
   else{
       cout << "No" << endl;
   }
}

Measured memory_bytes: 3580
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 100
using namespace std;
const int INF=0x3f3f3f3f;
char c[maxn][maxn];

int n,m;
struct node{
    int x,y;
};
node pre[maxn][maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int vis[maxn][maxn];
int coun=0;
void bfs(){
    queue<node>que;
    memset(vis,INF,sizeof(vis));
    node s;
    s.x=0,s.y=0;
    que.push(s);
    while(!que.empty()){
        node p=que.front();
        que.pop();
        if(p.x==n-1&&p.y==m-1) break;
        for(int i=0;i<4;i++){
            int xx=p.x+dx[i];
            int yy=p.y+dy[i];
            if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==INF&&c[xx][yy]=='.'){
                node now;
                now.x=xx,now.y=yy;
                que.push(now);
                pre[xx][yy]=p;
                //printf("//%d %d//\n",pre[xx][yy].x,pre[xx][yy].y);
                vis[xx][yy]=vis[p.x][p.y]+1;
            }
        }
    }
    if(vis[n-1][m-1]==INF){
        puts("-1");
        return;
    }
    while(que.empty()){
        que.pop();
    }
    int x=n-1,y=m-1;
    int cnt=1;
    while(1){
        if(x==0&&y==0) break;
        cnt++;
        int tmp1=x,tmp2=y;
        x=pre[tmp1][tmp2].x;
        y=pre[tmp1][tmp2].y;

    }
    printf("%d\n",n*m-cnt-coun);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",c[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(c[i][j]=='#'){
                coun++;
            }
        }
    }
    bfs();
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

template<typename T> class segtree {
private:
    int n,sz,h;
    vector<pair<T, int> > node;
    vector<T> lazy;
    void eval(int k) {
        if(lazy[k]){
            node[k].first += lazy[k];
            if(k < n) {
                lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k];
            }
            lazy[k] = 0;
        }
    }
 
public:
    segtree(const vector<T>& v) : sz((int)v.size()), h(0) {
        n = 1;
        while(n < sz) n *= 2, h++;
        node.resize(2*n, pair<T, int>(numeric_limits<T>::max(), sz));
        lazy.resize(2*n, 0);
        for(int i = 0; i < sz; i++){
            node[i+n] = make_pair(v[i], i);
        }
        for(int i = n-1; i >= 1; i--){
             node[i] = min(node[2*i], node[2*i+1]);
        }
    }
    void range(int a, int b, T x, int k=1, int l=0, int r=-1){
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            lazy[k] += x;
            eval(k);
        }else{
            range(a, b, x, 2*k, l, (l+r)/2);
            range(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = min(node[2*k], node[2*k+1]);
        }
    }
    pair<T, int> query(int a, int b) {
        a += n, b += n - 1;
        for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
        b++;
        pair<T, int> res1 = make_pair(numeric_limits<T>::max(), sz);
        pair<T, int> res2 = make_pair(numeric_limits<T>::max(), sz);
        while(a < b) {
            if(a & 1) eval(a), res1 = min(res1, node[a++]);
            if(b & 1) eval(--b), res2 = min(res2, node[b]);
            a >>= 1, b >>= 1;
        }
        return min(res1, res2);
    }
};

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll n, q;
	cin >> n >> q;
	vector<ll> v(n, 0);
	segtree<ll> sg(v);
	
	rep(i, 0, q){
		ll f;
		cin >> f;
		if(f == 0){
			ll s, t, x;
			cin >> s >> t >> x;
			sg.range(s, t+1, x);
		}
		else{
			ll s, t;
			cin >> s >> t;
			print(sg.query(s, t+1).first)
		}
	}
	return 0;
}


Measured memory_bytes: 9696
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define YY cout << "Yes" << endl
#define NN cout << "No" << endl
const int INF = 1000000007;
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
bool is_prime(long long n) {  //素数判定
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) return false;
  }
  return true;
}
int solve(){
  int n,x;
  cin >> n >> x;
  vector<ll>v(n);
  rep(i,n)cin >> v[i];
  ll ans = 0;
  rep(i,n - 1){
    ll tmp = v[i] + v[i + 1];
    if(tmp <= x)continue;
    if(tmp - v[i + 1] <= x){
      ans += tmp - x;
      v[i + 1] -= tmp - x;
    }
    else{
      ans += tmp - x;
      v[i + 1] = 0;
    }
  }
  cout << ans << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16) << endl; 
  solve();
  return 0;
} 

Measured memory_bytes: 1024
#include<stdio.h>

int main(void)
{
  //nを入力
  int n;
  scanf("%d",&n);

  //wを入力
  int i,w[n];
  for(i=0;i<n;i++)
    scanf("%d",&w[i]);

  int t,s1,s2,sub,ans=100;
  for(t=0;t<n;t++){

    //s1,s2を初期化
    s1 = 0;  s2 = 0;

    for(i=0;i<n;i++){
      //番号がt以下ならs1に加算
      if(t>=i)
        s1 += w[i];
      else
        s2 += w[i];
    }

    //差の絶対値をsubとする
    sub = s1-s2;
    if(sub<0)
      sub = -sub;

    //ansを更新
    if(sub<ans)
      ans = sub;
  }

  printf("%d\n",ans);
  return 0;
}

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

int main(){
	int N;
	scanf("%d", &N);
	long long A[N];
	for(int i=0;i<N;i++)scanf("%lld", &A[i]);
	long long ans = 0;
	for(long long i=2;i*i<=1000000000;i++){
		long long tmpans = 0;
		for(int j=0;j<N;j++)if(A[j]%i==0)tmpans+=A[j];
		ans=max(ans, tmpans);
	}
	long long B[N];
	for(int i=0;i<N;i++){
		B[i]=A[i];
		for(long long j=2;j*j<=1000000000;j++){
			while(B[i]%j==0)B[i]/=j;
		}
	}
	for(int i=0;i<N;i++){
		long long tmpans = 0;
		for(int j=0;j<N;j++){
			if(B[i]!=1&&A[j]%B[i]==0)tmpans += A[j];
		}
		ans=max(ans, tmpans);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3228
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long ;
const int MAXN = 1e5 ;
const ll MOD = 1e9 + 7 ;
int n , m ;
vector<bool> blocked ;
ll dp[MAXN] ;
ll dfs(int x){
    if ( x > n ) return 0 ;
    if ( x == n ) return 1 ;
    if ( blocked[x] ) return 0 ;
    if ( dp[x] != -1 ) return dp[x] ;
    dp[x] = ( dfs(x+1) + dfs(x+2) ) % MOD ;
    return dp[x] ;
}


int main(){
    memset(dp,-1,sizeof dp);
    cin >> n >> m ;
    blocked.resize(n) ;
    for(int i=0;i<m;i++){
        int x ;
        cin >> x ;
        blocked[x] = true ;
    }
    cout << dfs(0) << endl;
	return 0 ;
}


Measured memory_bytes: 4096
# AGC019B - Reverse and Compare
from collections import Counter


def main():
    S = input().rstrip()
    C, N = Counter(S).values(), len(S)
    ans = N * (N - 1) // 2 + 1  # all possible patterns
    ans -= sum(i * (i - 1) // 2 for i in C)  # duplicates
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3872
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
long long n;
vector<long long> BIT(200020);
void add(long long i, long long x) {
	while (i <= n) {
		BIT[i] += x;
		BIT[i] %= 998244353;
		i += i & -i;
	}
}
long long csum(long long i) {
	long long count = 0;
	while (i > 0) {
		count += BIT[i];
		count %= 998244353;
		i -= i & -i;
	}
	return count;
}
long long sum(long long l, long long r) {
	return csum(r) - csum(l - 1);
}
int l[20], r[20];
int main() {
	long long k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			add(i, 1);
		}
		else {
			add(i, 0);
		}
	}
	for (int i = 0; i < k; i++) {
		cin >> l[i] >> r[i];
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 0; i < k; i++) {
			add(j, sum(j - r[i], j - l[i]));
		}
	}
	long long ans = sum(n, n);
	while (ans < 0) {
		ans += 998244353;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4692
#include<bits/stdc++.h>
#define endl "\n"
#ifdef ONLINE_JUDGE
#define DEBUG(x)
#else
#define DEBUG(x) cout<<#x<<" : {"<<x<<"}"<<endl; 
#endif
using namespace std;
typedef long long int lli;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int x, n;
	int arr[200];
	cin>>x>>n;
	if(n == 0){
		cout<<x<<endl;
	}
	else{
	
		set<int> s;
		for(int i=0; i<n; ++i){	
			cin>>arr[i];
			s.insert(arr[i]);
		}
		int nearest;
		int num = x;
		while(1){
			num--;
			if(s.find(num) == s.end()){
				nearest = num;
				break;
			}
		}
		//DEBUG(nearest);
		num = x;
		while(1){
			num++;
			if(s.find(num) == s.end()){
				if(abs(num-x) < abs(nearest-x))
					nearest = num;
				break;
			}
		}
		if(s.find(x) == s.end())
			nearest = x;
		cout<<nearest<<endl;
	}
	
    return 0;
}


Measured memory_bytes: 3644
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)

    while (true) {
        val a = sc.nextInt()
        val op = sc.next()
        val b = sc.nextInt()
        if (op == "?") break
        val ans = when (op) {
            "+" -> a+b
            "-" -> a-b
            "*" -> a*b
            "/" -> a/b
            else -> throw IllegalStateException()
        }
        println(ans)
    }
}


Measured memory_bytes: 25456
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    ll A, B, N;
    cin >> A >> B >> N;
    if (N%B == 0) N--;
    ll x = min(B-1, N);
    ll ans = A * x / B - A * (x / B);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3588
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  long long ans = 0;
  for (int b = k + 1; b <= n; b++) {
    long long num = b - k;
    ans += (n / b) * num;
    if (k == 0) {
      ans += n % b;
    }
    if (k > 0 && n % b - (k - 1) > 0) {
      ans += n % b - (k - 1);
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
using ll = long long;


int main()
{
    char a, b;
    cin >> a >> b;
    if(a == 'H'){
        cout << b << endl;
    }else {
        cout << (b == 'H' ? 'D' : 'H') << endl;
    }
}

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

long long gcd(long long x, long long y) {
  long long r;
  if (x < y) swap(x, y);
  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

vector<pair<long long, long long>> pf(long long n) {
  vector<pair<long long, long long>> res;
  for (long long p = 2; p*p <= n; p++) {
    if (n % p != 0) continue;
    int num = 0;
    while (n % p == 0) { num++; n /= p; }
    res.push_back(make_pair(p, num));
  }
  if (n != 1) res.push_back(make_pair(n, 1));
  return res;
}

int main() {
  long long A, B; cin >> A >> B;
  long long x = gcd(A, B);
  vector<pair<long long, long long>> ans = pf(x);
  cout << ans.size() + 1LL << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
    int num,peb,i;
    while (1) {
        scanf("%d %d",&num,&peb);
        if (num==0&&peb==0) break;
        int cand[50]={0},bowl=0,flag;
        while (1) {
            if (peb>0) {
                cand[bowl]++;
                peb--;
            } else {
                peb=cand[bowl];
                cand[bowl]=0;
            }
            flag=0;
            if (peb==0&&cand[bowl]!=0) {
                flag=1;
                for (i=0; i<num; i++) {
                    if (i!=bowl&&cand[i]!=0) {
                        flag=0;
                        break;
                    }
                }
            }
            if (flag==1) {
                break;
            } else {
                if (bowl==num-1) {
                    bowl=0;
                } else {
                    bowl++;
                }
            }
        }
        printf("%d\n",bowl);
    }
    return 0;
}

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

long long mod = 1'000'000'007;

int dp[101][4][4][4];

void Main() {
  int n;
  cin >> n;

  memset(dp, 0, sizeof(dp));
  dp[0][3][3][3] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 4; j++) {
      for(int k = 0; k < 4; k++) {
        for (int l = 0; l < 4; l++) {
          if (dp[i][j][k][l] == 0) continue;
          for (int m = 0; m < 4; m++) {
            if (m == 2 && j == 1 && k == 0) continue;
            if (m == 2 && j == 0 && k == 1) continue;
            if (m == 1 && j == 2 && k == 0) continue;
            if (m == 2 && j == 1 && l == 0) continue;
            if (m == 2 && k == 1 && l == 0) continue;
            dp[i + 1][m][j][k] += dp[i][j][k][l];
            dp[i + 1][m][j][k] %= mod;
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        ans += dp[n][i][j][k];
        ans %= mod;
      }
    }
  }
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#define N1 1001
using namespace std;
int Change(string);
void DP();
int N,W,n,v[N1],w[N1],dp[N1][N1];
int main(){
  int t,len,i,j;
  string in;
  n=1;
  while(1){
    cin >> W;
    if(W==0) break;
    cin >> N;
    for(i=1;i<=N;i++){
      cin >> in;
      len=in.size();
      for(j=0;j<len;j++){
	if(in[j]==','){
	  t=j;
	  break;
	}
      }
      v[i]=Change(in.substr(0,t));
      w[i]=Change(in.substr(t+1,len-t-1));
    }
    DP();
  }
  return 0;
}
int Change(string s){
  int ret=0,len=s.size(),i=0,x=1;
  while(len){
    ret=ret*x+(s[i]-'0');
    x=10;
    i++;
    len--;
  }
  return ret;
}
void DP(){
  int i,j,sum[N1][N1],wsum;
  for(i=0;i<=W;i++) dp[0][i]=0,sum[0][i]=0;
  for(i=0;i<=N;i++) dp[i][0]=0,sum[i][0]=0;
  for(i=1;i<=N;i++){
    for(j=1;j<=W;j++){
      if(j>=w[i]){
	if(dp[i-1][j]<=dp[i-1][j-w[i]]+v[i]){
	  dp[i][j]=dp[i-1][j-w[i]]+v[i];
	  sum[i][j]=1;
	}else{
	  dp[i][j]=dp[i-1][j];
	  sum[i][j]=0;
	}
      }else{
	dp[i][j]=dp[i-1][j];
	sum[i][j]=0;
      }
    }
  }
  wsum=0;
  int cp=W;
  for(i=N;i>=1;i--){
    if(sum[i][cp]==1){
      wsum+=w[i];
      cp-=w[i];
    }
  }
  cout << "Case " << n << ':' << endl;
  n++;
  cout << dp[N][W] << endl << wsum  << endl;
}

Measured memory_bytes: 9040
#include <iostream>
using namespace std;
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; }
const long long INF = 1LL<<60;

// 入力
int N;
long long W, weight[110], value[110]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に

// DPテーブル
long long dp[110][100100] = {0};

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];

    // DPループ
    for (int i = 0; i < N; ++i) {
        for (int sum_w = 0; sum_w <= W; ++sum_w) {

            // i 番目の品物を選ぶ場合
            if (sum_w - weight[i] >= 0) {
                chmax(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i]);
            }

            // i 番目の品物を選ばない場合
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }

    // 最適値の出力
    cout << dp[N][W] << endl;
}

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

#define int long long

signed main(){
  int N, ans = 0;
  vector<int> A;

  cin>>N;

  A.resize(N);

  for(int i = 0;i < N; i++){
    cin>>A[i];
  }

  for(int i = 0, x = 1;i < N; i++){

    if(A[i] == x){
      ans += A[i]/x - 1;
        x++;
    } else {
      ans += A[i]/x;
      if(A[i]%x == 0) ans--;
      if(!i)x++;
    }
    //cout<<"i = "<<i<<" A = "<<A[i]<<" ans = "<<ans<<" x = "<<x<<endl;
  }

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


Measured memory_bytes: 1024