akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cctype>
using namespace std;

string toUpper(string s){
    string t = s;
    for(int i = 0; i < s.size(); i++){
        t[i] = toupper(s[i]);
    }
    return t;
}

int main(){
    string target, source;

    cin >> target;
    target = toUpper(target);

    int cnt = 0;

    while(1){
        cin >> source;
        if(source == "END_OF_TEXT") break;
        source = toUpper(source);
        if(target == source) cnt++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//�]���؂�グ�� =>  (a + b - 1) / b 

signed main(){
	long double a,b; cin>>a>>b;
  ll c=(a*b);
  cout<<c;
	
	return 0;
}

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

signed main(){

  int64_t n;
  cin>>n;

  if(n==0){cout<<0<<endl;return 0;}

  string ans = "";

  while(n){
    int r = abs(n%2);
    n -= r;
    n /= -2;
    ans += to_string(r);
  }
  reverse(begin(ans),end(ans));
  cout<<(ans)<<endl;

}

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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pop pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define bb begin()
#define ee end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;

int digit(int n)
{
    int m=0;

    while(n)
    {
        m+=(n%10);
        n/=10;
    }
    return m;
}



int arr[g_size];



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	string s1,s2;

	char s[100000];

	int ara[n_size],ara2[n_size];

	cin>>n;
	k=digit(n);
	((n%k))?cout<<"No"<<endl:cout<<"Yes"<<endl;

}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

# from heapq import heappush, heappop, heapify
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

graph = defaultdict(list)
# tree = UnionFind(N)
for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

# for a in graph[a-1]:
    # for b in graph[b-1]:
s = set(graph[0]) & set(graph[N-1])
# print(set(graph[0]))
# print(set(graph[N-1]))

if not s:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


#     tree.union(a-1, b-1)

# if tree.find(0) == tree.find(N-1):
#     print("POSSIBLE")
# else:
#     print("IMPOSSIBLE")




Measured memory_bytes: 104912
A=int(input())

B=int(input())

if((A==1 and B==2) or (A==2 and B==1)):
	print(3)
elif((A==2 and B==3) or (A==3 and B==2)):
	print(1)
elif((A==1 and B==3) or (A==3 and B==1)):
	print(2)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	ll n, m, a, b, cnt[200020] = {};
	cin >> n >> m;
	bool f = 0;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (a == 1)cnt[b]++;
		if (b == n)cnt[a]++;
		if (cnt[a] == 2)f = 1;
		if (cnt[b] == 2)f = 1;
	}
	cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
	return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        new Program().Calc();
    }

    Scanner cin;

    public Program() { }

    bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
    bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }

    void Calc()
    {
        cin = new Scanner();

        int k = cin.nextInt();
        int a = cin.nextInt();
        int b = cin.nextInt();

        bool ansFlag = false;

        for (int i = a; i <= b; ++i)
        {
            if (i % k == 0)
            {
                ansFlag = true;
                break;
            }
        }
        
        WriteLine(ansFlag? "OK":"NG");

    }
}

public static class StringExtension
{
    public static char GetChar1(this string str, int indexOneBase)
    {
        return str[indexOneBase - 1];
    }
}

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: 27480
#include <iostream>
using namespace std;

int main(){
    int N;
    cin>>N;
    int C[N][N];
    int64_t ans = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) cin>>C[i][j];
    }

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            ans+=min(C[i][j],C[j][i]);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3156
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head


const int N = 3e5+10;
int n,cnt,ans,x,l,v[N],w[N];
int dp[1<<9|1][N];
struct _ {
	int v,w;
} a[N];

void dfs(int d, int sum, int val) {
	if (sum>l) return;
	if (d==cnt) {
//		printf("d=%d,sum=%d,val=%d,dp[%d][%d]=%d\n",
//				d,sum,val,x,l-sum,dp[x][l-sum]);
		ans = max(ans, dp[x][l-sum]+val);
		return;
	}
	dfs(d+1,sum,val),dfs(d+1,sum+a[d].w,val+a[d].v);
}

int main() {
	scanf("%d", &n);
	REP(i,1,n) scanf("%d%d",v+i,w+i);
	int mx = min((1<<9)-1,n);
	REP(i,1,mx) {
		REP(j,0,N-1) dp[i][j]=dp[i/2][j];
		REP(j,w[i],N-1) dp[i][j]=max(dp[i][j],dp[i/2][j-w[i]]+v[i]);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &x, &l);
		cnt = ans = 0;
		while (x>mx) {
			a[cnt].v=v[x],a[cnt].w=w[x];
			++cnt;
			x/=2;
		}
		dfs(0,0,0);
		printf("%d\n", ans);
	}
}










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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

ll graph[101][101] = {{}}, d[101] = {}, n;

void bfs(int v) {
  queue<int> q;
  q.push(v);
  ll u;
  for(int i = 1; i <= n; i++) d[i] = -1;
  d[v] = 0;
  while(!q.empty()) {
    u = q.front(); q.pop();
    for(int i = 1; i <= n; i++) {
      if(graph[u][i] == 0) continue;
      if(d[i] != -1) continue;
      d[i] = d[u] + 1;
      q.push(i);
    }
  }
}

signed main() {
	ll u, v, k;
  cin >> n;
  rep(i, n) {
    cin >> u >> k;
    rep(j, k) {
      cin >> v;
      graph[u][v] = 1;
    }
  }

  bfs(1);

  for(int i = 1; i <= n; i++) {
    cout << i << " " << d[i] << endl;
  }

	return 0;
}


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

const ll MINF=-pow(10,18);
const ll INF=pow(10,18);

int main(void){
    int A,B,Q; cin >> A >> B >> Q;
    vector<ll> s(A+2), t(B+2), X(Q);
    s[0]=MINF; for(int i=0; i<A; i++) cin >> s[i+1]; s[A+1]=INF;
    t[0]=MINF; for(int i=0; i<B; i++) cin >> t[i+1]; t[B+1]=INF;
    for(int i=0; i<Q; i++) cin >> X[i];

    for(int i=0; i<Q; i++){
        ll x=X[i];
        auto it1=upper_bound(s.begin(), s.end(), x);
        ll sR=*it1; it1--;
        ll sL=*it1;
        auto it2=upper_bound(t.begin(), t.end(), x);
        ll tR=*it2; it2--;
        ll tL=*it2;

        ll a=x-min(sL,tL);
        ll b=max(sR,tR)-x;
        ll c=min(2*sR-x-tL, sR+x-2*tL);
        ll d=min(2*tR-x-sL, tR+x-2*sL);

        cout << min(min(a,b), min(c,d)) << endl;
        //cout << sL << " " << sR << " " << tL << " " << tR << endl;
    }
}


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(std::string T){
    rep(i, T.length()) if(T[i] == '?') T[i] = 'D';
    cout << T << endl;
}

struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    std::string T;
    std::cin >> T;
    solve(T);
    return 0;
}


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

using namespace std;
using ll = long long;

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    int N, M;
    cin>>N>>M;
    vector<int> X(M);
    for (int i = 0; i < M; i++) cin>>X[i];

    if(N>=M){
        cout<<0<<endl;
        return 0;
    }

    sort(all(X));

    vector<int> dif;
    for(int i = 1; i < M; i++)
    {
        dif.push_back(abs(X[i]-X[i-1]));
    }
    sort(all(dif));
    
    for(int i = 0; i < N-1; i++)
    {
        dif.pop_back();
    }
    
    ll sum=0;
    for(auto x : dif)sum+=x;
    cout<<sum<<endl;

    return 0;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
#define LL long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define MOD(x) ((x)%1000000007)

using namespace std;
const int maxn = 2e5 + 7;
LL tmp, X, sum[maxn];
int n;
int main()
{
    scanf("%d%lld", &n, &X);
    sum[0] = 0;
    double ans = 1e60;
    for(int i = 1; i <= n; i++) scanf("%lld", &tmp), sum[i] = sum[i - 1] + tmp;
    for(int k = 1; k <= n; k++)
    {
        double Tmp = 0;
        for(int i = n; i >= 0; i -= k)
        {
            if(i == n) Tmp += 5 * sum[i];
            else if(i + k == n) continue;
            else Tmp += 2 * sum[i];
        }
        Tmp += (k + n) * X;
        ans = min(ans, Tmp);
    }
    printf("%lld", (LL)ans);
    return 0;
}


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

int main(void){
    char c;
    cin>>c;
    bool ans=false;
    string vowel = "aiueo";
    for (int i=0;i<5;i++){
        if (vowel[i]==c) ans=true;
    }
    if (ans) cout<<"vowel"<<endl;
    else cout<<"consonant"<<endl;
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

const double PI=acos(-1.0);

int main()
{
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    double th = double(h*60+m)/720 * 2*PI;
    double tm = double(m)/60 * 2*PI;
    double rad = th - tm;
    double ans = double(a*a + b*b) - double(2*a*b) * cos(rad);
    ans = sqrt(ans);
    printf("%.10f\n", ans);

    return 0;
}

Measured memory_bytes: 4168
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int qty = sc.nextInt();
		int t = sc.nextInt();
		int a = sc.nextInt();
		double ts[] = new double[qty];
		for(int i = 0; i < qty; i ++) {
			ts[i] = t - sc.nextInt() * 0.006;
		}
		double best = Math.abs(ts[0] - a);
		int index = 0;
		for(int i = 0; i < qty; i ++) {
			if(Math.abs(ts[i] - a) < best) {
				best = Math.abs(ts[i] - a);
				index = i;
			}
		}
		System.out.println(index + 1);
	}
}

Measured memory_bytes: 22484
from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
C = [[int(i) for i in input().split()] for _ in range(10)]
A = []
for _ in range(H):
    A += [int(i) for i in input().split()]
D = dijkstra(C)
D = D[:, 1]
ans = 0
for x in A:
    if abs(x) != 1:
        ans += int(D[x])
print(ans)


Measured memory_bytes: 14516
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String  S = sc.next();
    
	if(S. equals ("SUN")){
		System.out.println("7");
	}else if(S. equals ("MON")){
		System.out.println("6");
	}else if(S. equals ("TUE")){
		System.out.println("5");
	}else if(S. equals ("WED")){
		System.out.println("4");
	}else if(S. equals ("THU")){
		System.out.println("3");
	}else if(S. equals ("FRI")){
		System.out.println("2");		
	}else {
		System.out.println("1");
		}
	}
}


Measured memory_bytes: 22868
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
 

signed main(){
	
	int n;
	string s,t;
	cin>>n>>s>>t;
	vector<int> cond;

	rep(i,n){
		if(s[i]==s[i+1]){
			cond.push_back(1);
			i++;
		}
		else cond.push_back(0);
	}
	int ans;
	if(cond[0]==1)ans=6;
	else ans=3;
	
	for(int i=1;i<cond.size();i++){
		if(cond[i-1]==1){
			if(cond[i]==1)ans*=3;
			ans%=MOD;
			//if(s[i]==0)ans
		}
		if(cond[i-1]==0){
			if(cond[i]==1)ans*=2;
			if(cond[i]==0)ans*=2;
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
// -D_GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// #include "../../Template.cpp"
const int mod = (1e9) + 7;
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    // dp[i][j] - ways of distributing j candies among i students
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            if (j == 0)
            {
                dp[i][j] = 1;
                continue;
            }
            if (arr[i - 1] >= j)
            {
                dp[i][j] += dp[i - 1][j];
            }
            else
            {
                dp[i][j] += dp[i - 1][j] - dp[i - 1][j - arr[i - 1] - 1];
            }
            dp[i][j] += dp[i][j - 1];
            dp[i][j] %= mod;
            dp[i][j] = (dp[i][j] + mod)%mod;
        }
    }
    // cout << dp << endl;
    cout << dp[n][k] % mod << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 80256
#include <iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <string>
#include <set>
#include <bitset>

using namespace std;
#define ff(i,n,m) for(int i=n;i<m;i++)
#define i64 int64_t
#define tos(x) to_string(x)

int main() {
	string o, e;
	cin >> o >> e;
	ff(i, 0, e.size()) {
		cout << o.at(i) << e.at(i);
	}
	if (o.size() > e.size()) {
		cout << o.at(o.size() - 1) << endl;
	}
	return 0;
}

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

using Int = int;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

int main(){
	std::string s;
	std::string add[2];
	bool rev = false;
	cin >> s;
	int q;
	cin >> q;
	RC(i, q){
		int t;
		cin >> t;
		if(t == 1){
			rev ^= true;
		}else{
			int f;
			char c;
			cin >> f >> c;
			add[(f == 2) ^ rev].push_back(c);
		}
	}
	if(rev == false){
		for(auto i = add[0].rbegin(); i != add[0].rend(); ++i) cout << *i;
		for(auto i = s.begin(); i != s.end(); ++i) cout << *i;
		for(auto i = add[1].begin(); i != add[1].end(); ++i) cout << *i;
		cout << endl;
	}else{
		for(auto i = add[1].rbegin(); i != add[1].rend(); ++i) cout << *i;
		for(auto i = s.rbegin(); i != s.rend(); ++i) cout << *i;
		for(auto i = add[0].begin(); i != add[0].end(); ++i) cout << *i;
		cout << endl;
	}
}


Measured memory_bytes: 1088
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;


public class Main{
	
	public static void main(String[] args){
		
		List<Integer> input = null;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){
			input = new ArrayList<Integer>();
			for(int j = 0; j < 10; j++){
				input.add(sc.nextInt());
			}
			List<Integer> l1 = removeList(input);
			input.removeAll(l1);
			Comparator<Integer> c = new Comparator<Integer>(){
				
				@Override
				public int compare(Integer o1, Integer o2){
					if(o1 < o2)
						return -1;
					else if(o1 == o2)
						return 0;
					else
						return 1;
				}
			};
			if(isSorted(l1, c) && isSorted(input, c))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
		sc.close();
	}
	static List<Integer> removeList(List<Integer> li){
		List<Integer> result = new ArrayList<Integer>();
		int lastIndex = 0;
		result.add(li.get(lastIndex));
		for(int i = lastIndex; i < li.size(); i++) {
			if(li.get(i) > li.get(lastIndex)) {
				result.add(li.get(i));
				lastIndex = i;
			}
		}
		
		return result;
	}
	
	static boolean isSorted(List<Integer> li, Comparator<Integer> c) {
		for(int i = 0; i < li.size() - 1; i++) {
			if(c.compare(li.get(i), li.get(i+1)) != -1) return false;
		}
		return true;
	}
}

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

int main() {
    int a, b, c, t;

    cin >> a >> b >> c;

    if (b < a) {
        t = a;  a = b;  b = t;
    }
    if (c < a) {
        t = a;  a = c;  c = t;
    }
    if (c < b) {
        t = b;  b = c;  c = t;
    }

    cout << a << " " << b << " " << c << endl;

    return 0;
}


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

typedef long long ll;
typedef long double ld;

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

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

int main(){

    ll A, B ,C;

    cin >> A >> B >> C;

    cout << (A <= C && C <= B ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int A, B;
  int max;
  scanf("%d %d", &A, &B);
  max = A + B;
  if((A - B) > max){
    max = A - B;
  }
  if((A*B) > max){
    max = A*B;
  }
  printf("%d\n", max);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int,int>;
constexpr ll mod = 1000000007;
void pPRINTl(ostream& ost) { ost << endl; }
template <class T>void pPRINTL(ostream& ost,T t){ost<<t<<endl;}
template <class T, class... U>void pPRINTl(ostream& ost, T t, U... u) {ost << t << " ";pPRINTl(ost, u...);}
template <class... T>void PRINTl(T... t) { pPRINTl(cout, t...); }
//#define PRINTl //
void pPRINT(ostream& ost) {}
template <class T>void pPRINT(ostream& ost, T t){ost<<t;}
template <class T, class... U>void pPRINT(ostream& ost, T t, U... u) {ost << t << " ";pPRINT(ost, u...);}
template <class... T>void PRINT(T... t) { pPRINT(cout, t...); }
 
 
 
int main(){
  
  ll n;
  cin>>n;
  ll a[n];
  REP(i,n){cin>>a[i];}
  ll max=-1,premax=-1;
  REP(i,n){
    if(max<a[i]){
      max=a[i];
    }
    else if(premax<a[i])premax=a[i];
  }
  REP(i,n){
    PRINTl((max==a[i]?premax:max));
  }
  return 0;
}

Measured memory_bytes: 3328
import java.util.*;

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

        int k = scan.nextInt();
        ArrayDeque<Long> q = new ArrayDeque<>();
        for(long i=1; i<=9; i++)
        {
            q.add(i);
        }
        long tmp = 0;
        for(int i=0; i<k; i++)
        {
            tmp = q.poll();
            if(tmp%10!=0)
            {
                q.add(tmp*10+tmp%10-1);
            }
            q.add(tmp*10+tmp%10);
            if(tmp%10!=9)
            {
                q.add(tmp*10+tmp%10+1);
            }
        }
        System.out.println(tmp);
    }
}

Measured memory_bytes: 29140
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

typedef vector<int> Node;
typedef vector<Node> Graph;

const int INF = 1000000000;

int add(Graph& G, int u){
    int v = G.size();
    G[u].push_back(v);
    G.push_back(Node());
    G[v].push_back(u);
    return v;
}
void bellman_ford(const Graph& G, int s, int dist[1000]){
    dist[s] = 0;
    bool update = true;
    while(update){
        update = false;
        for(int i = 0; i < G.size(); i++){
            for(int j = 0; j < G[i].size(); j++){
                int k = G[i][j];
                if(dist[k] > dist[i] + 1){
                    dist[k] = dist[i] + 1;
                    update = true;
                }
            }
        }
    }
}

int main(){
    int N;
    while(cin >> N && N){
        int d[100][100] = {};
        int dist[100][1000] = {};
        REP(i, 100) fill(dist[i], dist[i] + 1000, INF);
        int start[100] = {};
        REP(i, N) REP(j, N) cin >> d[i][j];
        REP(i, N) REP(j, N) d[i][j] -= 2;

        Graph G;
        G.push_back(Node());
        start[0] = 0;
        dist[0][0] = 0;

        for(int i = 1; i < N; i++){
            vector<int> v;
            for(int j = 0; j < i; j++){
                v.push_back(d[i][j]);
            }

            int u = -1;
            int len = -1;
            for(int j = 0; j < G.size(); j++){
                set<int> s;
                for(int k = 0; k < v.size(); k++){
                    s.insert(v[k] - dist[k][j]);
                }
                if(s.size() == 1){
                    u = j;
                    len = *s.begin();
                }
            }

            assert(u != -1);
            assert(len >= 0);
            while(len--){
                u = add(G, u);
            }
            start[i] = u;
            //printf("start[%d] = %d\n", i, u);

            for(int j = 0; j <= i; j++){
                bellman_ford(G, start[j], dist[j]);
            }
        }
        vector<int> ans;
        for(int i = 0; i < G.size(); i++){
            ans.push_back(G[i].size());
        }
        for(int i = 0; i < N; i++){
            ans[ start[i] ]++;
        }
        sort(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i];
            if(i == ans.size() - 1) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 1720
#include<iostream>
using namespace std;
int ans;
int main(){
	string s;
	cin>>s;
	if (s=="SUN")	ans=7;
	else if (s=="MON")	ans=6;
	else if (s=="TUE")	ans=5;
	else if (s=="WED")	ans=4;
	else if (s=="THU")	ans=3;
	else if (s=="FRI")	ans=2;
	else if (s=="SAT")	ans=1;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
/**
 *   Author: Praveen Ojha
 *   Created: 29 March 2019
 *   Time: 19:38:12
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vvi vector<vector<int> >
#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__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
const int INF=1e18+5;
//vvi dp(405,vi (405));
int32_t main(){__
	int n;
	cin>>n;
	vi a(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	vvi dp(n,vi (n,0));
	   for(int L = n - 1; L >= 0; L--){
        for(int R = L; R < n; R++){
			if(L==R){
				dp[L][R]=0;
			}
			else
			{
				dp[L][R]=INF;
				int sumi=0;
				for(int i=L;i<=R;i++)
					{
						sumi+=a[i];
					}
				for(int i=L;i<=R-1;i++){
					dp[L][R]=min(dp[L][R],dp[L][i]+dp[i+1][R]+sumi);
				}
			}
		}
	}
	debug() << imie(dp) ;
	cout<<dp[0][n-1]<<"\n";
return 0;
}

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

int main() {
  int k; cin>>k;
  vector<long long> a(k);
  for (int i = 0; i < k; i++) cin>>a[i];

  long long ma = 2, mi = 2;
  for (int i = k-1; i >= 0; i--) {
    long long d = a[i] - mi % a[i];
    if (d != a[i] and mi + d > ma) {
      cout << -1 << endl;
      return 0;
    }
    mi = mi % a[i] == 0 ? mi / a[i] * a[i] : (mi / a[i] + 1) * a[i];
    ma = ma / a[i] * a[i] + a[i] - 1;
  }

  cout << mi << ' ' << ma << endl;

  return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<ll> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];
  sort(v.begin(), v.end());
  vector<ll> ans;
  for (int i = v.size() - 1; i > 0; i--) {
    if (v[i] == v[i - 1]) {
      ans.push_back(v[i]);
      i--;
    }
  }
  sort(ans.begin(), ans.end());
  if (ans.size() < 2) {
    cout << 0 << endl;
  } else {
    cout << ans[ans.size() - 1] * ans[ans.size() - 2] << endl;
  }
}


Measured memory_bytes: 1660
n = gets.chomp.to_i
akes = 0
tojis = 0
tojiake = []
n.times{|i|
  ake_count = 0
  toji_count = 0
  gets.chomp.split('').each{|v|
    if v == '('
      ake_count += 1
    else
      if ake_count > 0
        ake_count -= 1
      else
        toji_count += 1
      end
    end
  }

  if toji_count == 0
    akes += ake_count
  elsif ake_count == 0
    tojis += toji_count
  else
    tojiake.push([toji_count, ake_count])
  end
}

hiraki = akes

success = true
# p tojiake.sort{|a, b| (b[1] - b[0]) <=> (a[1] - a[0]) }
tojiake.sort{|a, b| (b[1] - b[0]) <=> (a[1] - a[0]) }.each{|i|
  hiraki -= i[0]
  if hiraki < 0
    success = false
    break
  end
  hiraki += i[1]
}
success = false if hiraki != tojis

puts success ? 'Yes' : 'No'


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

int main() {
	int n, m; cin >> n >> m;
	vector<int>road(n,0);
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2; cin >> tmp1 >> tmp2;
		road[tmp1-1]++; road[tmp2-1]++;
	}
	for (auto&& x : road) {
		cout << x << endl;
	}

	return 0;
}

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

int main(){
    int N;
    int max_n=20;
    int c[max_n];
    int v[max_n];
    int b[max_n];
    int benefit=0;

    cin >> N;
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    for(int i=0;i<N;i++){
        cin>>c[i];
    }
    for(int i=0;i<N;i++){
        b[i]=v[i]-c[i];
        if(b[i]>0){
            benefit+=b[i];
        }
        else{
            ;
        }
    }
    cout<<benefit;
    return 0;
}

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

#define int long long

signed main(){
	constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
	int n;
	cin >> n;
	map<int, int> m;
	for(int i = n + 1; --i;){
		int tmp = i;
		for(int j = 0; j < sizeof(primes) / sizeof(primes[0]); j++){
			while(tmp % primes[j] == 0){
				m[primes[j]]++;
				tmp /= primes[j];
			}
		}
		if(tmp != 1) m[tmp]++;
	}
	int ans = 1;
	for(auto itr = m.begin(); itr != m.end(); itr++) (ans *= itr->second + 1) %= (long long)(1e9) + 7;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define X real()
#define Y imag()
#define pb push_back
#define all(c) c.begin(),c.end()
#define show(x) cout<<#x<<" : "<<x<<endl
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
D inf=1e50,eps=1e-10,pi=acos(0.0)*2;
bool eq(D a,D b){
	return abs(a-b)<eps;
}
bool compxy(const P& l,const P& r){
	return eq(l.X,r.X) ? l.Y<r.Y : l.X<r.X;
}
bool on(L l,P p){
	return (eq(abs(l.fs-p)+abs(l.sc-p),abs(l.fs-l.sc)));
}
int N,M;
int sx,sy,gx,gy;
vector<L> lines;
vector<P> points;
vector<P> online[200];
vector<int> ans;
bool sign[200];
int ne[200][200];
D d[200][200];
int id(P p){
	return lower_bound(all(points),p,compxy)-points.begin();
}
int pre[200];
D dist[200];
void dijkstra(int s){
	bool used[200]={};
	rep(i,M) dist[i]=inf;
	dist[s]=0;
	rep(i,M){
		int u=-1;
		rep(j,M) if(!used[j]&&(u==-1||dist[u]>dist[j])) u=j;
		if(u==-1) break;
		used[u]=true;
		rep(j,M){
			if(dist[j]>dist[u]+d[u][j]){
				dist[j]=dist[u]+d[u][j];
				pre[j]=u;
			}
		}
	}
}
int main(){
	while(true){
		cin>>N;
		if(N==0) break;
		lines.clear();
		points.clear();
		ans.clear();
		rep(i,N) sign[i]=false;
		rep(i,N) online[i].clear();
		cin>>sx>>sy>>gx>>gy;
		rep(i,N){
			int x,y,z,w;
			cin>>x>>y>>z>>w;
			lines.pb(L(P(x,y),P(z,w)));
		}
		rep(i,N){
			P &a=lines[i].fs,&b=lines[i].sc;
			bool aon=false,bon=false;
			rep(j,N) if(i!=j&&on(lines[j],a)) aon=true;
			rep(j,N) if(i!=j&&on(lines[j],b)) bon=true;
			if(!aon||!bon) sign[i]=true;
			else{
				points.pb(a);
				points.pb(b);
				rep(j,N){
					if(on(lines[j],a)) online[j].pb(a);
					if(on(lines[j],b)) online[j].pb(b);
				}
			}
		}
		sort(all(points),compxy);
		points.erase(unique(all(points)),points.end());
		M=points.size();
		rep(i,N) if(!sign[i]){
			sort(all(online[i]),compxy);
			online[i].erase(unique(all(online[i])),online[i].end());
		}
		rep(i,M) rep(j,M) if(i!=j) d[i][j]=inf;
		rep(i,N) if(!sign[i]){
			rep(j,online[i].size()-1){
				int x=id(online[i][j]),y=id(online[i][j+1]);
				d[x][y]=d[y][x]=abs(online[i][j]-online[i][j+1]);
			}
		}
/*		rep(i,N) if(!sign[i]){
			rep(j,online[i].size()) cout<<online[i][j]<<"  ";
			cout<<endl;
		}*/
		rep(i,N) if(sign[i]){
			P &a=lines[i].fs,&b=lines[i].sc;
			rep(j,N) if(!sign[j]){
				if(on(lines[j],b)) swap(a,b);
				if(on(lines[j],a)){
//					show(a);
//					rep(k,online[j].size()) cout<<online[j][k]<<endl;
//					int iid=lower_bound(all(online[j]),a,compxy)-online[j].begin();
//					show(iid);
					P y=*lower_bound(all(online[j]),a,compxy),x=*(lower_bound(all(online[j]),a,compxy)-1);
					D theta=abs(arg((b-a)/(y-x)));
					D a=theta-pi/2.0;
					if(a<=eps) d[id(x)][id(y)]=inf;
					if(a>=-eps) d[id(y)][id(x)]=inf;
				}
			}
		}
		int s=id(P(sx,sy)),g=id(P(gx,gy));
		dijkstra(s);
		if(dist[g]==inf){
			puts("-1");
			continue;
		}
		while(s!=g){
			ans.pb(g);
			g=pre[g];
		}
		ans.pb(s);
		rep(i,ans.size()){
			int x=ans[ans.size()-1-i];
			cout<<(int)points[x].X<<" "<<(int)points[x].Y<<endl;
		}
		puts("0");
	}
}

Measured memory_bytes: 1560
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first 
#define ss second  
typedef pair<int,int> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
} 
int N=1e5+9;
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int a,b; 
	cin>>a>>b;
	cout<<a*b;
	return 0; 
	
}


Measured memory_bytes: 3616
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
	int a;
	cin>>a;
	double b;
	vector<double> v;
	for(int i=0;i<a;i++){
		cin>>b;
		v.push_back(b);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<a-1;i++){
		v.push_back((v[0]+v[1])/2);
		v.erase(v.begin(),v.begin()+2);
		sort(v.begin(),v.end());
	}
	cout<<v[0]<<endl;
	return 0;
}

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

    long int n;
    cin >> n;
    vector<long int> a(n);
    map <long int, long int> aCnt;

    rep(i,n) {
        cin >> a.at(i);
        aCnt[a.at(i)]++;
    }

    map <long int, long int> comb;

    long int allcomb;
    for(auto x = aCnt.begin(); x != aCnt.end(); ++x){
        allcomb += (x->second * (x->second -1)) / 2;
    }

    rep(i,n){
        long int tmp = aCnt[a.at(i)];
        tmp = (tmp-1) * (tmp-2) / 2  - (tmp * (tmp-1) / 2);
        long int ans = allcomb + tmp;
        cout << ans << endl;
    }

}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define print(x) cout << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T> >
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int N;
ll C;
ll x[101010], v[101010];
ll y[101010];
ll A[101010], B[101010], D[101010];

ll solve() {
  A[0] = v[0];
  //時計回りの累積和
  srep(i, 1, N) A[i] = A[i - 1] + v[i];

  rep(i, N) y[i] = C - x[i];
  B[N - 1] = v[N - 1];
  //半時計回りの累積和
  drep(i, N - 1) B[i] = B[i + 1] + v[i];

  D[N - 1] = B[N - 1] - y[N - 1];
  //D[i]:=左にi個までのお寿司を食べたときの、カロリーの最大値
  drep(i, N - 1) {
    D[i] = B[i] - y[i];
    maxs(D[i], D[i + 1]);
  }

  ll ans = 0;
  rep(i, N) {
    ll sm = 0;
    sm -= x[i];  // →移動
    sm += A[i];  // →カロリー
    maxs(ans, sm);
    sm -= x[i];  // 原点に戻る
    if (i < N - 1) sm += D[i + 1];
    maxs(ans, sm);
  }

  return ans;
}
int main() {
  cin >> N >> C;
  rep(i, N) cin >> x[i] >> v[i];

  ll ans = 0;
  maxs(ans, solve());

  reverse(v, v + N);
  rep(i, N) x[i] = C - x[i];
  reverse(x, x + N);

  maxs(ans, solve());
  cout << ans << endl;
}

Measured memory_bytes: 4992
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

void solve(long long N){
    if (N % 2) cout << N * 2 << '\n';
    else cout << N << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int W[N+1];
  W[0] = 0;
  for(int i=1;i<N+1;i++) cin >> W[i];
  int S[N+1]={0};
  S[0]=0;
  for(int i=1;i<N+1;i++) S[i]=S[i-1]+W[i];
  int ans = S[N];
  for(int i=1;i<N+1;i++)
    if(ans>abs(S[N]-2*S[i]))
      ans = abs(S[N]-2*S[i]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
prime = [2]
for i in range(10000):
    if i == 0 or i == 1 or i == 2:
        continue
    a = True
    for p in prime:
        if i % p == 0:
            a = False
            break
    if a == True:
        prime.append(i)
n = input()
a = []
for p in prime:
    if p % 5 == 1:
        a.append(p)
        if len(a) == n:
            break
b = ''
for c in a:
    b += str(c) + ' '
b = b[:-1]
print b


Measured memory_bytes: 2948
#include <math.h>
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
const int MGN = 10;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long; using ull = unsigned long long;
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 vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using psl = pair<string, ll>;

int N;
string S;
set<int> st;
vector<vvb> dp;

void dfs(int n, int l, int p) {
  if (l>=3) {
    assert(l==3);
    st.insert(p);
    return;
  }
  if (n>=N) return;

  if (dp[n][l][p]) return;

  dfs(n+1, l, p);
  if (l<3 && p*10+(S[n]-'0') < 1000) {
    dfs(n+1, l+1, p*10+(S[n]-'0'));
  }

  dp[n][l][p] = true;
}

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


  cin>>N;
  S; cin>>S;

  dp = vector<vvb>(N, vvb(4, vb(1000, false)));
  // [0,i] で j 文字を選んで、パスを k にできるか
  dfs(0, 0, 0);

  int ans = st.size();
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 25472
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
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;}

const int INF = 19191919;

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

    int s = 0;
    for(int i=1; i<=n; ++i) s += L+i-1;

    int d = INF;
    int ans = INF;
    for(int i=1; i<=n; ++i){
        int x = 0;
        for(int j=1; j<=n; ++j)if(i!=j) x += L+j-1;

        int t = abs(x - s);
        if(t < d){
            ans = x;
            d = t;
        }
    }

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


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

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


signed main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 1;
    char c = s[0];
    for(int i = 1; i < n; ++i)
        if(s[i] != c){
            c = s[i];
            ++ans;
        }
    cout << ans << endl;
}


Measured memory_bytes: 512
import Control.Monad

solver::[(Int,Int)]->Int
solver ls = let left = map fst ls in
            let right = map snd ls in
            max 0 ((minimum right) + 1 - (maximum left))

main::IO()
main=do
  _:n:_ <- return.map read.words =<< getLine
  dat<-forM [1..n] (\_ -> return .  (\ (l:r:_) -> (l,r)) . map read . words =<< getLine )
  print (solver dat)


Measured memory_bytes: 85372
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }

    vector<int> l_sum((1 << n), 0), bit_cnt((1 << n), 0);
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) > 0) {
                l_sum[i] += l[j];
                bit_cnt[i]++;
            }
        }
    }

    int mp_min = (1 << 30);
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 1; j < (1 << n); j++) {
            for (int k = 1; k < (1 << n); k++) {
                if ((i & j) > 0 || (j & k) > 0 || (k & i) > 0) {
                    continue;
                }

                int mp = 10 * (bit_cnt[i] + bit_cnt[j] + bit_cnt[k] - 3)
                    +abs(a - l_sum[i]) + abs(b - l_sum[j]) + abs(c - l_sum[k]);
                if (mp_min > mp) {
                    mp_min = mp;
                }
            }
        }
    }

    cout << mp_min << endl;
}


Measured memory_bytes: 256
K, A, B = map(int, input().split())

if A >= B:
    print(K + 1)
else:
    # A < B
    have = 1
    if (A - have) <= K:   
        K -= (A - have)
        have = A
        
        rep = K // 2
        tataku = K % 2
        rep_add = max(B - A, 2)
        have += rep_add * rep
        have += tataku
    else:
        have += K        
    print(have)


Measured memory_bytes: 3060
n = int(input())

List = [int(i) for i in input().split()]
    
for i in range(1,n):
    for k in range(n-1):
        print(List[k], end=" ")
    print(List[n-1])
    j = i-1
    v = List[i]
    while j >= 0 and List[j] > v:
        List[j+1] = List[j]
        j-=1
    List[j+1] = v

for k in range(n-1):
    print(List[k], end=" ")
print(List[n-1])



Measured memory_bytes: 5980