akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

int h, w;
const int maxn = 190;
string a[maxn];
int f[maxn][maxn][maxn][20];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> h >> w;
    for(int i = 0;i < h;i++){
        cin >> a[i];
        for(int j = w - 1;j >= 0;j--){
            if(j == w - 1){
                f[i][i][j][0] = 1;
            }else{
                if(a[i][j] == a[i][j + 1]){
                    f[i][i][j][0] = f[i][i][j + 1][0] + 1;
                }else{
                    f[i][i][j][0] = 1;
                }
            }
        }
    }
    for(int j = 0;j < w;j++){
        for(int l = 0;l < h;l++){
            for(int r = l + 1;r < h;r++){
                if(a[l][j] == a[r][j]){
                    f[l][r][j][0] = min(f[l][r - 1][j][0], f[r][r][j][0]); 
                }else{
                    f[l][r][j][0] = 0;
                }
            }
        }
    }
    for(int S = 1;S <= 16;S++){
        for(int j = 0;j < w;j++){
            for(int l = 0;l < h;l++){
                for(int r = l, m = l;r < h;r++){
                    for(;m < r and min(f[l][m][j][S - 1], f[m+1][r][j][S - 1]) <= min(f[l][m+1][j][S - 1], f[m+2][r][j][S - 1]);m++) ;
                    f[l][r][j][S] = f[l][r][j][S - 1];
                    int len = f[l][r][j][S - 1];
                    f[l][r][j][S] = max(f[l][r][j][S], len + f[l][r][j + len][S - 1]);
                    f[l][r][j][S] = max(f[l][r][j][S], min(f[l][m][j][S - 1], f[m+1][r][j][S - 1]));    
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i <= 16;i++){
        if(f[0][h - 1][0][i] == w){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 504064
n=int(input())
a=list(map(int,input().split()))
li = [0]*9
for i in a:
  if i < 400:
    li[0]+=1
  elif i < 800:
    li[1]+=1
  elif i < 1200:
    li[2]+=1
  elif i < 1600:
    li[3]+=1
  elif i < 2000:
    li[4]+=1
  elif i < 2400:
    li[5]+=1
  elif i<2800:
    li[6]+=1
  elif i<3200:
    li[7]+=1
  else:
    li[8]+=1
li_ = [i for i in li[:-1] if i>0]
num = len(li_)
if num==0:
  print(1,n)
else:
  print(num, num + li[-1])


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

int main(void)
{
  string s;
  cin >> s;

  if(s=="Sunny"){
    cout << "Cloudy" << endl;
  }else if(s=="Cloudy"){
    cout << "Rainy" << endl;
  }else{
    cout << "Sunny" << endl;
  }
}



Measured memory_bytes: 256
def read_inputs
  r, c = gets.split(" ").map(&:to_i)
  (1..r).map { gets.split(" ").map(&:to_i)}
end

def sum_row(row)
  row << row.inject(:+)
end

def sum_column(table)
  table.transpose.map {|c| c.inject(:+)}
end

table = read_inputs
puts table.map{|r| sum_row(r).join(" ")}.join("\n")
puts sum_column(table).join(" ")

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

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

  if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }
  return 0;
}


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

int main()
{
    ll n,T,i,j,k;
    cin>>n>>T;
    ll t[n+1];
    for(i=0;i<n;i++)
    {
        cin>>t[i];
    }
    ll ans = 0;
    for(i=0;i<n-1;i++)
    {
        if(t[i+1]-t[i]<=T)
        {
            ans += t[i+1] - t[i];
        }
        else
        {
            ans += T;
        }
    }
    ans += T;
    
    cout<<ans<<endl;
    return 0;
}

//1125899906842623


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s1[2017],s2[2017];
int n,ans,tx=0,lst[2017],nxt[2017],maxx[2017];
bool vis[2017],vis1[2017],vis2[2017];
struct data {
	int x,y;
}a[2017];
void pre_lst_nxt() {
	int now=0;
	for (int i=1;i<=n;i++) {
		if (s2[i-1]=='1') now=i;
		lst[i]=now;
	}
	for (int i=1;i<=n;i++) if (lst[i]==0) lst[i]=now;
	now=0;
	for (int i=n;i>=1;i--) {
		if (s2[i-1]=='1') now=i;
		nxt[i]=now;
	}
	for (int i=1;i<=n;i++) if (nxt[i]==0) nxt[i]=now;
}
int dist(int l,int r) {
	if (l<=r) return r-l;
	return r+n-l;
}
bool cmp(data p,data q) {
	return p.x<q.x;
}
void work(int x) {
	int step=0;
	for (int i=1;i<=n;i++) {
		vis[i]=vis1[i]^(s2[i-1]=='1');
		if (vis[i]) step++;
	}
	for (int i=1;i<=n-x;i++) vis2[i]=vis[i+x];
	for (int i=n-x+1;i<=n;i++) vis2[i]=vis[i-n+x];
	tx=0;
	for (int i=1;i<=n;i++) {
		if (!vis2[i]) continue;
		int nowx=dist(lst[i],i);
		int nowy=dist(i,nxt[i]);
		if (nowy<=x) continue;
		a[++tx].x=nowx;
		a[tx].y=nowy-x;
	}
	sort(a+1,a+tx+1,cmp);
	maxx[tx+1]=0;
	for (int i=tx;i>=1;i--) maxx[i]=max(maxx[i+1],a[i].y);
	a[0].x=0;
	for (int i=0;i<=tx;i++) ans=min(ans,2*(a[i].x+maxx[i+1])+x+step);
	x=n-x;
	tx=0;
	for (int i=1;i<=n;i++) {
		if (!vis2[i]) continue;
		int nowx=dist(lst[i],i);
		int nowy=dist(i,nxt[i]);
		if (nowx<=x) continue;
		a[++tx].x=nowx-x;
		a[tx].y=nowy;
	}
	sort(a+1,a+tx+1,cmp);
	maxx[tx+1]=0;
	for (int i=tx;i>=1;i--) maxx[i]=max(maxx[i+1],a[i].y);
	a[0].x=0;
	for (int i=0;i<=tx;i++) ans=min(ans,2*(a[i].x+maxx[i+1])+x+step);
}
int main() {
	scanf("%s%s",s1,s2);
	n=strlen(s1);
	bool equal=1;
	for (int i=0;i<n;i++) if (s1[i]!=s2[i]) {
		equal=0;
		break;
	}
	if (equal) {
		printf("0\n");
		return 0;
	}
	int cnt=0;
	for (int i=0;i<n;i++) if (s2[i]=='1') cnt++;
	if (cnt==0) {
		printf("-1\n");
		return 0;
	}
	pre_lst_nxt();
	for (int i=0;i<n;i++) if (s1[i]=='1') vis1[i+1]=1;
	ans=1e9;
	work(0);
	for (int i=1;i<n;i++) {
		bool last=vis1[n];
		for (int j=n;j>=2;j--) vis1[j]=vis1[j-1];
		vis1[1]=last;
		work(i);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  cin >> N >> K;
  
  int seisuu =1;
  
  int i = 0;
  
  while (i < N) {
    if (seisuu >= K) {
      break;
    }
    seisuu *= 2;
    i++;
  }
  
  while (i < N) {
    seisuu += K;
    i++;
  }
  
  cout << seisuu << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
	int N,L;
	int i,j;

	scanf("%d",&N);
	scanf("%d",&L);

	char S[N][L+1];

	for(i=0;i<N;i++){
		scanf("%s",S[i]);
	}

	char tmp[L+1];

	for(i=1; i<N; i++){
		for(j=N-1; j>=i; j--){
			if(strcmp(S[j-1], S[j]) > 0){
				strcpy(tmp, S[j-1]);
				strcpy(S[j-1], S[j]);
				strcpy(S[j], tmp);
			}
		}
	}
	
	for(i=0;i<N;i++){
		printf("%s",S[i]);
	}

	return 0;
}

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

int main(){
    int N;
    cin >> N;
    string ans;
    switch(N%7){
        case 0 : ans = "thu"; break;
        case 1 : ans = "fri"; break;
        case 2 : ans = "sat"; break;
        case 3 : ans = "sun"; break;
        case 4 : ans = "mon"; break;
        case 5 : ans = "tue"; break;
        case 6 : ans = "wed"; break;
    }
    cout << ans << endl;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N;
    string S;
    cin >> N >> S;
    ll res = 0;
    REP(i, N-2){
    	if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt() % 10;
        String ans = "";
        if(n == 2 || n == 4 || n == 5 || n == 7 || n == 9){
            ans = "hon";
        }else if(n == 3){
            ans = "bon";
        }else{
            ans = "pon";
        }
        System.out.println(ans);
    }
}



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

int main(){
    int s,m,h,a,b;
    cin>>s;
    m=s/60;
    h=m/60;
    a=m*60;
    s-=a;
    b=h*60;
    m-=b;
    cout<<h<<":"<<m<<":"<<s<<endl;
    
}


Measured memory_bytes: 3088
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

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

        public static void Solve()
        {
            var nm = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
            var ai = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
            var result = nm[0] - ai.Sum();
            Console.WriteLine(result >= 0 ? result : -1);
        }
    }
}


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

using namespace std;

int main()
{
	vector<int> isp(150001,1);
	isp[0]=isp[1]=0;
	for(int i=2;i*i<isp.size();i++)
		for(int j=i*i;j<isp.size();j+=i)
			isp[j]=0;
	vector<int> ps;
	for(int i=0;i<isp.size();i++) if(isp[i])
		ps.push_back(i);
	
	for(int n,p;cin>>n>>p,~(n&p);){
		vector<int> cs;
		int o=upper_bound(ps.begin(),ps.end(),n)-ps.begin();
		for(int i=0;i<p;i++)
			for(int j=i;j<p;j++)
				cs.push_back(ps[o+i]+ps[o+j]);
		sort(cs.begin(),cs.end());
		cout<<cs[p-1]<<endl;
	}
	
	return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int f(int a, int b) {
  if(a > b) swap(a, b);
  if(a == b) return a;
  return 2*a+f(a, b-a);
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, X;
  cin >> N >> X;
  //assert(N <= 1000);
  //cout << f(N-X, X)+N << endl;
  cout << 3*(N-__gcd(N, X)) << endl;

  return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
p1=1/N
p2=1/2
ans=0
for i in range(1,N+1):
    if i<K:
        p=p1
        while i<K:
            p=p*p2
            i=2*i
        ans+=p
    else:
        ans+=p1
print(ans)        
        
    

Measured memory_bytes: 2940
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()


s=input().rstrip()
ans=""
for i in range(len(s)):
    if s[i]=="B":
        ans=ans[:len(ans)-1]
    else:
        ans+=s[i]
print(ans)


Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;
typedef pair<int, P> PP;

signed main() {
	int f; cin >> f;
	cout << (f - 30) / 2 << endl;
}



Measured memory_bytes: 3084
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    def dfs(c, x):
        if len(c) == N:
            print(c)
        else:
            nx = ord(x)-ord('a')
            for i in range(nx+1):
                if i == nx:
                    dfs(c+chr(ord('a')+i), chr(ord(x)+1))
                else:
                    dfs(c+chr(ord('a')+i), x)
    dfs('', 'a')
resolve()

Measured memory_bytes: 4412
import java.util.Scanner;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int D = Integer.parseInt(scan.next());
		int T = Integer.parseInt(scan.next());
		int S = Integer.parseInt(scan.next());

		if (D <= T*S) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 35736
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        StringBuilder build = new StringBuilder();
        int z = sc.nextInt();
        int[] ary = new int[z];
        for(int i = 0 ; i < ary.length; i++){
            ary[i] = sc.nextInt();
        }
        int count = 0;
        for(int j = 0; j < ary.length; j++){
            for(int i = ary.length-1; i > j; i--){
                if(ary[i] < ary[i-1]){
                    int temp = ary[i];
                    ary[i] = ary[i-1];
                    ary[i-1] = temp;
                    count++;
                }
            }
        }
        for(int i = 0; i < ary.length; i++){
            build.append(ary[i]);
            build.append(i==ary.length-1 ? "\n" : " ");
        }
        build.append(count);
        System.out.println(build.toString());
    }
}

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

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

    priority_queue<long long> que;
    for (int i=0; i<n; ++i) {
        long long a;
        cin >> a;
        que.push(a);
    }

    for (int i=0; i<m; ++i) {
        que.push(que.top()/2);
        que.pop();
    }

    long long ans = 0;
    for (int i=0; i<n; ++i) {
        ans += que.top();
        que.pop();
    }

    cout << ans << '\n';
}

Measured memory_bytes: 1400
import math
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

a,b,x=MI()
dega=0
degb=90
i=0
while i<100:
    deg=(dega+degb)/2
    sita=math.radians(deg)
    v1=a*a*b-a**3/2*(math.tan(sita))
    v2=a*b*b/2/(math.tan(sita))
    if math.tan(sita)>=(b/a):
        v=v2
    else:
        v=v1
    if v==x:
        ans=deg
        print(ans)
        sys.exit()
    if v>x:
        dega=deg
    if v<x:
        degb=deg
    i=i+1
    #print(deg)
print(deg)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

class Point {
public:
    double x,y;

    Point(double x=0,double y=0):x(x),y(y) {}
    Point operator + (Point p) {return Point(x+p.x,y+p.y);}
    Point operator - (Point p) {return Point(x-p.x,y-p.y);}
    Point operator * (double a) {return Point(a*x,a*y);}
    Point operator / (double a) {return Point(x/a,y/a);}

    double abs() {return sqrt(norm());}
    double norm() {return x*x+y*y;}

    bool operator<(const Point &p) const {
        return x!=p.x ? x<p.x : y<p.y;
    }
    bool operator==(const Point &p) const {
        return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
    }
};

struct Segment {
    Point p1,p2;
};

typedef Point Vector;

double dot(Vector a,Vector b) {
    return  a.x*b.x+a.y*b.y;
}

Point project(Segment s,Point p) {
    Vector base=s.p2-s.p1;
    double r=dot(p-s.p1,base)/base.norm();
    return s.p1+base*r;
}

int main(void) {
    struct Segment s;
    cin>>s.p1.x>>s.p1.y>>s.p2.x>>s.p2.y;
    int q;
    cin>>q;
    while(q) {
        Point p;
        cin>>p.x>>p.y;
        Point ans=project(s,p);
        printf("%.10f %.10f\n",ans.x,ans.y);
        q--;
    }
    return 0;
}

Measured memory_bytes: 3176
#include "bits/stdc++.h"
#include <unordered_set>

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define INF 1000000000
#define PI 3.14159265358979323846

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

// N, E, S, W
const int dx[4] = { -1, 0,  1,  0 };
const int dy[4] = { 0, 1,  0, -1 };

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<LL> vll;

//==============================================

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

	int h;
	cin >> h;

	vi A(h);

	REP(i, h) cin >> A[i];
	make_heap(ALL(A));
	
	cout << " ";
	REP(i, h) {
		if (i) cout << " ";
		cout << A[i];
	}
	cout << "\n";
	return 0;
}

Measured memory_bytes: 4508
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N;
	cin >> N;

	ll kotae = 0;
	rep1(i, N) {
		kotae += (N - 1) / i;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

int main(void)
{
	double a, b, c, d, e, f;
	double x, y;
	
	while (scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF){
		y = (c * d - a * f) / (b * d - a * e);
		x = (c - b * y) / a;
		
		printf("%.3lf %.3lf\n", x, y);
	}
	
	return (0);
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
#define INF (1e17)
#define N 505
#define C 51
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;

vector<P> G[N];
ll n,m,x,y,t,v0,a,b,c;
ll d[C][N],cp[C][N];
priority_queue<P1,vector<P1>,greater<P1> > q;

ll dijkstra(int s,int g,int v){
  for(int i=0;i<c;i++)
    for(int j=0;j<n;j++)d[i][j]=INF;
  q.push(P1(0,P(v,s)));
  d[v][s]=0;
  while(!q.empty()){
    P1 temp=q.top(); q.pop();
    ll cost=temp.first;
    ll V=temp.second.first;
    ll node=temp.second.second;
    if(d[V][node]<cost)continue;
    for(int i=0;i<G[node].size();i++){
      ll ncost=cost+G[node][i].second*V;
      ll nnode=G[node][i].first;
      ll nV=(a*V+b)%c;
      if(d[nV][nnode]>ncost){
	d[nV][nnode]=ncost;
	q.push(P1(ncost,P(nV,nnode)));
      }
    }
  }
  ll res=INF;
  for(int i=0;i<c;i++)
    res=min(res,d[i][g]);
  return res;
}

void solve(){
  dijkstra(0,n-1,v0);
  for(int i=0;i<c;i++)
    for(int j=0;j<n;j++)cp[i][j]=d[i][j];

  ll ans=INF;
  for(int i=0;i<c;i++){
    if(cp[i][n-1]==INF)continue;
    ans=min(ans,cp[i][n-1]+dijkstra(n-1,0,i));
  }
  cout<<ans<<endl;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>x>>y>>t;
    G[x-1].push_back(P(y-1,t));
    G[y-1].push_back(P(x-1,t));
  }
  cin>>v0>>a>>b>>c;
  
  solve();
  return 0;
}

Measured memory_bytes: 6220
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            cnt = 0
            for i in range(max(h-1, 0), min(h+2, H)):
                for j in range(max(w-1, 0), min(w+2, W)):
                    if S[i][j] == "#":
                        cnt += 1
            S[h][w] = str(cnt)
    print("".join(S[h]))

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

int main() {
	int N, Q, A[10000], B[500];
	int counter = 0;
	
	cin >> N;
	for ( int i = 0; i < N; i++) scanf("%d", &A[i]);
	
	cin >> Q;
	for ( int i = 0; i < Q; i++) scanf("%d", &B[i]);
	
	for (int i = 0; i < Q; i++) {
		for (int j = 0; j < N; j++){
			if (B[i] == A[j]) {
				counter++;
				break;
			}
		}
	}
	
	cout << counter << endl;
	return 0;
}


Measured memory_bytes: 3184
#include<bits/stdc++.h>
#define M 1000000007
#define pi ld(acos(-1.0))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n) for(int i=1;i<(int)(n);i++)
#define repp(i,a,b)  for(ll i=a;i<=(ll)(b);i++)
#define Repp(i,a,b)  for(int i=a;i>=(int)(b);i--)
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define ii pair<int,int>
#define bye(x) {cout<<x;return 0;}
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    cs
    int n;cin>>n;
    vector<int> v(n);
    vector<int> vv(n);
    rep(i,n) cin>>v[i]>>vv[i];
    sort(v.begin(),v.end());
    sort(vv.begin(),vv.end());
    if(n&1) cout<<vv[n/2]-v[n/2]+1;
    else cout<<vv[n/2]+vv[n/2-1]-(v[n/2]+v[n/2-1])+1;
}

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

const int MOD = 1000000007;
using Data = pair<long long, vector<ll> >;

int main() {
  ll n,x;
  cin >> n >> x;
  ll ans=0;
  vector<ll>vec(n);
  rep(i,n) cin >> vec[i];
  rep(i,n){
    if(vec[i]>x){
      ans+=vec[i]-x;
      vec[i]=x;
    }
  }
  rep(i,n-1){
    if(vec[i]+vec[i+1]>x){
      ans+=vec[i]+vec[i+1]-x;
      vec[i+1]=max((ll)0,x-vec[i]);
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ld> >
#define vl vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;
#include <iomanip>

int main(int argc, char const *argv[]) {
  ld n;
  std::cin >> n;
  vvl xy = vv(n, 2, 0, ld);
  for(int i=0;i<n;i++) std::cin >> xy[i][0] >> xy[i][1];
  ld ans = 0;
  if(n==2){
    ld o = sqrt((xy[0][0]-xy[1][0])*(xy[0][0]-xy[1][0])+(xy[0][1]-xy[1][1])*(xy[0][1]-xy[1][1]));
    std::cout << fixed << setprecision(20) << o << '\n';
    exit(0);
  }
  std::vector<ld> fact(10, 1);
  for(ld i=2;i<10;i++) fact[i] = fact[i-1] * i;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j) continue;
      ans += sqrt((xy[i][0]-xy[j][0])*(xy[i][0]-xy[j][0])+(xy[i][1]-xy[j][1])*(xy[i][1]-xy[j][1])) * fact[n-2] * (n-1);
    }
  }
  ld o = ans/fact[n];
  std::cout << fixed << setprecision(20) << o << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[3][110];
int a[3][110];
int main(void)
{
    int n;
    cin>>n;
    dp[1][0]=0;
    for(int i=1;i<=2;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cin>>a[i][j];
            if(i==1)
            {
                dp[i][j]=dp[i][j-1]+a[i][j];
            }
        }
    }
    dp[2][1]=dp[1][1]+a[2][1];

    for(int j=2;j<=n;++j)
    {
        dp[2][j]=max(dp[2][j-1],dp[1][j]);
        dp[2][j]+=a[2][j];
    }
    cout <<dp[2][n]<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int keta(int number){
	int n=0;
	while(number!=0){
		number=number/10;
		n++;
	}
	return n;
}

int main(){
	int n,i,m,j,count;
	char *str,*newstr,*strstock,chk;
	scanf("%d",&n);
	while(n!=0){
		str=(char *)malloc(sizeof(char)*101);
		scanf("%s",str);
		for(j=0;j<n;j++){
		m=strlen(str);
		newstr=(char*)malloc(sizeof(char));
		newstr[0]='\0';
		for(i=0;i<m;i++){
			chk=str[i];
			count=1;
			while(str[i+1]==chk){
				count++;
				i++;
			}
			strstock=(char*)malloc(sizeof(char)*(strlen(newstr)+1));
			strcpy(strstock,newstr);
			//printf("strstock : %s\n",strstock);
			free(newstr);
			newstr=(char*)malloc(sizeof(char)*(strlen(strstock)+keta(count)+2));
			//newstr[0]='\0';
			sprintf(newstr,"%s%d%c",strstock,count,chk);
			//printf("%d %c\n",count,chk);
			//printf("newstr :%s\n",newstr);
			free(strstock);
		}
		free(str);
		str=(char*)malloc(sizeof(char)*(strlen(newstr)+1));
		strcpy(str,newstr);
		free(newstr);
		//printf("%s\n",str);
		}
		printf("%s\n",str);
		free(str);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 756
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    N,K = map(int, readline().split())

    prepare(N, MOD)

    ans = 0
    for i in range(min(N-1, K)+1):
        ans += modcmb(N, i, MOD) * modcmb(N-1, i, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


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

#define REP(i,n) for(decltype(n) i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) ((int)((c).size()))
#define st first
#define nd second
#define pb push_back

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

bool check(int i, int k, int size, const vi& v){
    vb b(v.size(), true);
    int j=i;
    for(;i<SIZE(v);++i){
        if(!b[i])
            continue;
        for(;j<SIZE(v);++j){
            if(!b[j]) continue;
            if(v[j]-v[i]>=k) break;
        }
        if(j<SIZE(v)){
            b[j]=false;
            while(j+2<SIZE(v)){
                b[j+1]=b[j+2]=false;
                j+=2;
            }
        } else if(size-v[i]<k)
            return false;
    }
    return true;
}

bool ok(int k,const vi& v,int size){
    return check(0,k,size,v) || check(1,k,size,v);
}

void solve(){
    string s;
    cin>>s;
    char cur=-1;
    vi num;
    REP(i, SIZE(s)){
        if(s[i]!=cur){
            num.pb(i);
            cur=s[i];
        }
    }
    int l=1, r=SIZE(s);
    while(l<r){
        int m=(l+r+1)/2;
        if(ok(m,num,SIZE(s)))
            l=m;
        else
            r=m-1;
    }
    cout<<l;
}

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


Measured memory_bytes: 720
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Edge{
  int v, cost; //頂点, コスト
  int times; //枝のコストを変えた回数
  Edge(int v, int cost) : v(v), cost(cost) {}
  Edge(int v, int cost, int times) : v(v), cost(cost), times(times) {}
  bool operator < (const Edge& e) const {
    if(times != e.times) return times > e.times;
    return cost > e.cost;
  }
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

int main(){
  int N, M, C;
  while(cin >> N >> M >> C && N){
    Graph G(N);
    REP(i, M){
      int f, t, c; cin >> f >> t >> c;
      f--; t--;
      G[f].push_back(Edge(t, c));
    }
    priority_queue<Edge> que;
    int dist[100][100] = {};
    REP(i, N)REP(j, N) dist[i][j] = INF;
    que.push(Edge(0, 0, 0));
    dist[0][0] = 0;
    while(!que.empty()){
      int u = que.top().v;
      int cost = que.top().cost;
      int times = que.top().times;
      que.pop();
      if(u == N - 1 && cost <= C) {
        cout << times << endl;
        break;
      }
      if(dist[u][times] < cost) continue;
      FORIT(e, G[u]){
        if(dist[e->v][times] > cost + e->cost){
          dist[e->v][times] = cost + e->cost;
          que.push(Edge(e->v, cost + e->cost, times));
        }
        if(times + 1< N && dist[e->v][times + 1] > cost){
          dist[e->v][times + 1] = cost;
          que.push(Edge(e->v, cost, times + 1));
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1284
def solve(v, u, k):
    sign_v = sign_u = 1
    swap = 1
    if abs(v) < abs(u):
        v, u = u, v
        swap = -1
    if v < 0:
        v = -v
        sign_v = -1
    if u < 0:
        u = -u
        sign_u = -1
    if v % k == 0:
        n = v // k
        res = []
        cum_u = 0
        for i in range(n):
            du = min(k, max(-k, u-cum_u))
            if (k+du)%2:
                du += 1 if du < 0 else -1
            cum_u += du
            res.append([k*sign_v, du*sign_u][::swap])
        assert cum_u == u, (cum_u, u)
        return res
    elif v < k and v%2==0:
        res = [[k, u-k], [v-k, k]]
        res = [[dv * sign_v, du * sign_u][::swap] for dv, du in res]
        return res
    else:
        m = v % k
        if (k+m)%2:
            m -= 1
        res = [[m, k]] + solve(v-m, u-k, k)
        res = [[dv*sign_v, du*sign_u][::swap] for dv, du in res]
        return res

def test():
    inf = -1
    M = [[inf]*1000 for _ in range(1000)]
    K = 9
    q = [(0, 0)]
    R = 100
    ans = 1
    M[0][0] = 0
    while q:
        q_new = []
        for x, y in q:
            for i in range(-K, K+1, 2):
                ux = x+i
                uy = y+i
                if -R <= ux <= R:
                    if y + K <= R:
                        if M[ux][y+K] == inf:
                            M[ux][y+K] = ans
                            q_new.append((ux, y+K))
                    if y - K >= -R:
                        if M[ux][y-K] == inf:
                            M[ux][y-K] = ans
                            q_new.append((ux, y-K))
                if -R <= uy <= R:
                    if x + K <= R:
                        if M[x+K][uy] == inf:
                            M[x+K][uy] = ans
                            q_new.append((x+K, uy))
                    if x - K >= -R:
                        if M[x-K][uy] == inf:
                            M[x-K][uy] = ans
                            q_new.append((x-K, uy))
        q = q_new
        ans += 1
    for x in range(-R, R+1):
        for y in range(-R, R+1):
            if M[x][y] != -1:
                if len(solve(x, y, K)) != M[x][y]:
                    print(f"!! x={x} y={y} len(solve(x, y, K))={len(solve(x, y, K))} M[x][y]={M[x][y]}")
    print("test finished")

#test()

def main():
    K = int(input())
    X, Y = map(int, input().split())
    if K % 2 == 0 and (X + Y) % 2:
        print(-1)
        exit()
    V, U = X + Y, X - Y
    Ans = solve(V, U, K)
    print(len(Ans))
    cum_x = cum_y = 0
    for v, u in Ans:
        x, y = (v+u)//2, (v-u)//2
        assert abs(x)+abs(y) == K
        cum_x += x
        cum_y += y
        print(f"{cum_x} {cum_y}")
    assert cum_x == X and cum_y == Y

main()


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

using namespace std;

typedef long long int Int;

Int city[300][300];
Int dist[300][300];
bool check[300][300];

bool exist(int start,int end,int n)
{
    bool flag = true;
    for(int i = 0;i < n;i++) {
	if(start == i || i == end)
	    continue;
	if(dist[start][i]+dist[i][end] == city[start][end])
	    flag = false;
    }

    return flag;
}

int main(void)
{
    Int n;
    cin>>n;

    for(int i = 0;i < n;i++) {
	for(int j = 0;j < n;j++) {
	    Int temp;
	    cin>>temp;

	    city[i][j] = temp;
	}
    }

    for(int i = 0;i < n;i++) {
	for(int j = 0;j < n;j++) {
	    check[i][j] = false;
	    if(i != j)
		dist[i][j] = 2e9;
	    else
		dist[i][j] = 0;
	}
    }

    for(int i = 0;i < n;i++) {
	for(int s = 0;s < n;s++) {
	    for(int e = 0;e < n;e++) {
		Int mini = dist[s][e];
		Int maxi = city[s][i]+city[i][e];
		if(mini < maxi)
		{
		    dist[s][e] = mini;
		} else {
		    dist[s][e] = maxi;
		}
	    }
	}
    }

    Int ans = 0;
    bool flag = false;
    for(int i = 0;i < n;i++) {
	for(int j = 0;j < n;j++) {
	    if(dist[i][j] == city[i][j])
	    {
		if(check[i][j])
		    continue;
		if(!exist(i,j,n))
		    continue;
		check[i][j] = check[j][i] = true;
		ans += dist[i][j];
	    }
	    else
		flag = true;
	}
    }

    if(flag)
	cout<<-1<<endl;
    else
	cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

char str[5];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        sprintf(str,"%d",n);
        if(str[0]==str[2])  puts("Yes");
        else                puts("No");
    }
    return 0;
}


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

// macros
#define pb emplace_back
#define mk make_pair
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define bit(n) (1LL<<(n))
// functions
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << p.first << " " << p.second; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
//  types
using ll = long long int;
using P = pair<int, int>;
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
// io
struct fast_io{
  fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);}
} fast_io_;


int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  double res = (double)(n - n / 2) / (double)n;
  cout << res << endl;
  return 0;
}


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

using namespace std;

#define vi vector<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case %d: ",a)

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

// bit manipulations

//bool checkbit(int mask,int bit){return mask & (1<<bit);}

//int setbit(int mask,int bit){ return mask  (1<<bit) ; }

//int clearbit(int mask,int bit){return mask & ~(1<<bit);}

//int togglebit(int mask,int bit){return mask ^ (1<<bit);}

#define mxn 100005
vi v;

i64 dp[102][2 * mxn];
i64 cum[2 * mxn];

i64 f(int pos,int sum) {
    if(pos == v.sz) {
        if( !sum)
            return 1;
        return 0;
    }
    if( sum < 0) return 0;

    i64 ans = 0;
    For(i,v[pos] + 1)
        ans += f(pos + 1 , sum - i);

    return dp[pos][sum] = ans;
}


int main()
{
    int n,k,inp;

    sff(n,k);
    while(n--) {
        sf(inp);
        v.pb(inp);
    }
//    mem(dp,-1);
//    cout << f(0,k) << endl;

    dp[v.sz][0] = 1;
    mem(cum,0);
    for(int i = 1 ; i <  mxn ; i++) {
        cum[i] += cum[i-1] + dp[v.sz][i - 1];
        cum[i] %= mod;
    }

    for(int pos = v.sz - 1 ; pos >= 0 ; pos--) {
        // l = sum - v[pos] , r = sum
        for(int sum = 0 ; sum < mxn ; sum++) {
            int l = max(0,sum - v[pos]);
            int r = sum;
            dp[pos][sum] = (cum[r + 1] - cum[l] + mod ) % mod;
        }

        mem(cum,0);
        for(int i = 1 ; i <  mxn ; i++) {
            cum[i] += cum[i-1] + dp[pos][i-1];
            cum[i] %= mod;
        }


    }

//    For(pos,5)
//    {
//        For(sum,10)
//                cout << dp[pos][sum] << ":";
//        cout << endl;
//
//    }

    cout << dp[0][k] << endl;



    return 0;
}



Measured memory_bytes: 160000
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << min({a + b, b + c, c + a}) << endl;
    return (0^_^0);
}



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

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999999;
	
	public static void Main(string[] args)
	{
		var p = Console.ReadLine();
		if(p == "ABC")
		{
		Console.WriteLine("ARC");
		
		}
		else
		
		Console.WriteLine("ABC");
		
	}
	
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	}
}

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

// n文字目以降の文字がうまく切れるかを計算
bool dfs(int n, vector<string> &v, string S){
  if(n == S.size()){
    return true;
  }
  for(auto str: v){
    if(n + str.size() <= S.size() && S.substr(n, str.size()) == str){
      if(dfs(n + str.size(), v, S)){
        return true;
      }
    }
  }
  return false;
}

int main(){
  vector<string> v = {"dream", "dreamer", "erase", "eraser"};

  string S;
  cin >> S;

  if(dfs(0, v, S)){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(vec) vec.begin(), vec.end()
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}

int main(){
  ll n; cin >> n;
  vector<ll> p(n); rep(i, n) cin >> p[i];
  
  //string ans = "Yes";
  //string ans = "No";
  //string ans = "YES";
  //string ans = "NO";
  ll ans = 0;
  vector<pair<ll, ll>> s(n);
  rep(i, n){
    s[i] = make_pair(p[i], i + 1);
  }
  sort(all(s));
  
  //cout << ans << endl;
  rep(i, n){
    cout << s[i].second;
    if (i < n - 1) cout << " ";
    else cout << endl;
  }
}

Measured memory_bytes: 3200
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    l = []
    n = []
    cnt = 0
    for i in range(len(s)):
        n.append(s[i])
        if l == n:
            n.append(s[i])
        else:
            l = list("".join(n))
            n = []
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 42952
// practice with Dukkha
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100000, K = 29, MD = 1000000007;

int ff[N + K], gg[N + K];

int power(long long a, int k) {
	long long p = 1;
	while (k) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
		k >>= 1;
	}
	return p;
}

void init(int n) {
	for (int f = 1, i = 0; i < n; i++) {
		gg[i] = power(ff[i] = f, MD - 2);
		f = (long long) f * (i + 1) % MD;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

int main() {
	int n, m; cin >> n >> m;
	int k = 0;
	while (1 << k + 1 <= m)
		k++;
	init(n + k);
	long long ans = 1;
	for (int p = 2; p <= m / p; p++)
		if (m % p == 0) {
			k = 0;
			while (m % p == 0) {
				k++;
				m /= p;
			}
			ans = ans * choose(n - 1 + k, k) % MD;
		}
	if (m > 1)
		ans = ans * n % MD;
	cout << ans << '\n';
	return 0;
}


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

#define FOR(i,a,b) for(size_t i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

typedef pair<ll, ll> pll;
// const ll INF = (ll)1e18;

signed main() {
	int x, y, z;
	cin >> x >> y >> z;
	int res = ((x - z) / (y + z));
	cout << res << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<numeric>
#include<iomanip>
using namespace std;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r) { return l.second < r.second; }
bool greaterPair(const ipair& l, const ipair& r) { return l.second > r.second; }
int main()
{
	int a, b, c, k; cin >> a >> b >> c >> k;
	int maX = max(a, b);
	maX = max(maX, c);
	int sum = a + b + c - maX + maX * pow(2, k);
	cout << sum << endl;
}


Measured memory_bytes: 512
#include<cstdio>
const int mod=1000000007;
int n,c[105],al[105],ar[105],f[105][105][55];
int dfs(int l,int r,int t){
	if(t==1)return 1;
	if(f[l][r][t])return f[l][r][t]-1;
	f[l][r][t]=dfs(l+al[t-1],r+ar[t-1],t-1);
	for(int i=1;i<=l+al[t-1];i++)(f[l][r][t]+=dfs(l-i+al[t-1],r+1+ar[t-1],t-1))%=mod;
	for(int i=1;i<=r+ar[t-1];i++)(f[l][r][t]+=dfs(l+1+al[t-1],r-i+ar[t-1],t-1))%=mod;
	return f[l][r][t]++;
}
int main(){
	scanf("%d",&n);
	int i=n*2,x;
	while(--i)scanf("%d",&x),c[x]++;
	for(i=1,x=0;x+c[i]<n;x+=c[i++])if(c[i])al[x+c[i]]++;
	for(i=n*2-1,x=0;x+c[i]<n;x+=c[i--])if(c[i])ar[x+c[i]]++;
	printf("%d\n",dfs(0,0,n));
}

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

#define rep(X,N) for(ll X = 0LL; X < (N); X++)
#define PI (acos(-1.0))
#define MODN 1000000007
#define MODN2 998244353
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;

int main(){

    int n;
    cin >> n;

    vector<ll> a(n + n + n);

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

    sort(ALL(a));

    ll ans = 0;

    for(int i = 0; i < n; i++){
        ans += a[(n * 3 - 2) - i * 2];
    }

    cout << ans << endl;

    return 0;
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

struct city{
  string a;
  int b,idx;
};

bool sorter(const city& x,const city& y){
  if(x.a==y.a)return x.b > y.b;
  else return x.a < y.a;
}

int N;
vector<city> ps;

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

  cin>>N;
  rep(i,N){
    string a;
    int b;
    cin>>a>>b;
    ps.push_back((city){a,b,i});
  }
  sort(all(ps),sorter);

  rep(i,N){
    cout<<ps[i].idx+1<<endl;
  }

  return 0;
}


Measured memory_bytes: 256