akhauriyash/Code-Regression huggingface dataset:
import  bisect
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

Ans=[-1]#0ではない

for i in range(n):
    #l=len(Ans)
    #for j in range(len(Ans)):
        #if i<j:
    #    if j!=l-1:
    #        if Ans[j]<a[i]<Ans[j+1]:
    #            Ans[j+1]=a[i]
                #print(*Ans)
    #    elif Ans[j]<a[i]:
    #        Ans.append(a[i])
    l=bisect.bisect_left(Ans,a[i])
    if l==len(Ans):
        Ans.append(a[i])
    else:
        Ans[l]=a[i]

#print(*Ans)

print(len(Ans)-1)



Measured memory_bytes: 10352
# coding: utf-8
# Your code here!
# TP1_3_B

# N=input()
# print(N)
N=-1
# while N != 0:
#     N=int(input())
#     print(N)
for i in range(1,10001):
    N=int(input())
    if N == 0:
        break
    print('Case {0}: {1}'.format(i,N))


Measured memory_bytes: 5600
N = int(input())
s = input()
t = input()
flag = True
for i in range(N):
    if s[i:] == t[:(N-i)]:
        flag = False
        break
if flag:
    print(len(s + t))
elif i == 0:
    print(len(s))
else:
    print(len(s[:i]) + N)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  string s,t;
  cin >> s >> t;
  int a=s.size();
  int b=t.size();
  int ans=1000000;
  rep(i,a-b+1){
    int cnt=0;
    rep(j,b){
      if(s[i+j]!=t[j])cnt++;
    }
    //cout << cnt << endl;
    ans=min(ans,cnt);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include<algorithm>
#include<typeinfo>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
#include<functional>
#include<bitset>
#include<stack>
#define e exp(1)
#define eps 0.01
#define pi acos(-1)
using namespace std;
typedef long long ll;
string s, t;
int main() {
    while (cin >> s >> t) {
        s += s;
        if (s.find(t) != s.npos)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
bingo = [list(map(int, input().split())) for _ in range(3)]
ls = [int(input()) for _ in range(int(input()))]

for i in range(3):
    for j in range(3):
        if bingo[i][j] in ls:
            bingo[i][j] = 1
        else:
            bingo[i][j] = 0

if sum(bingo[0]) == 3 or sum(bingo[1]) == 3 or sum(bingo[2]) == 3:
    print('Yes')
    exit()

if sum(bingo[i][0] for i in range(3)) == 3 or sum(bingo[i][1] for i in range(3)) == 3 or sum(bingo[i][2] for i in range(3)) == 3:
    print('Yes')
    exit()

if bingo[0][0] + bingo[1][1] + bingo[2][2] == 3 or bingo[0][2] + bingo[1][1] + bingo[2][0] == 3:
    print('Yes')
    exit()

print('No')


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

#define ll long long
#define pb push_back
#define endl '\n'
#define fcin ios::sync_with_stdio(false); cin.tie(nullptr);
#define inf 0x3f3f3f3f

int main(){
    fcin;
    int a[5];
    for(int i = 0; i < 5; i++) cin >> a[i];
    int k;  cin >> k;
    int ans = 0;
    for(int i = 0; i < 5; i++){
        for(int j = i+1; j < 5; j++){
            if(a[j] - a[i] > k) ans++;
        }
    }
    cout << (!ans ? "Yay!" : ":(");
    return 0;
}




Measured memory_bytes: 256
e1,e2,e3,e4=map(int,input().split())

if e1==e2:
    if e3==e4:
        print("yes")
    else:
        print("no")
elif e1==e3:
    if e2==e4:
        print("yes")
    else:
        print("no")
else:
    if e2==e3:
        print("yes")
    else:
        print("no")



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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  long tmp = 0;
  for (auto a : A) tmp ^= a;
  for (auto a : A) cout << (a ^ tmp) << "\n";
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define PI (acos(-1))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define MAXN 1123456
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;

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

  int n, m;
  cin >> n >> m;
  if (m >= n) {
    cout <<   "Yes\n";
  } else cout << "No\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
struct R{int start;int finish;string era;};


int main(){
	struct R R1[1005];
	int N,Q;
	while(cin>>N>>Q){

		for(int i=0;i<N;i++){
			int w;
			cin>>R1[i].era>>w>>R1[i].finish;
			R1[i].start=R1[i].finish-w;
		}
		int y;
		for(int i=0;i<Q;i++){
			cin>>y;bool f=false;
			for(int j=0;j<N;j++)
			{if(R1[j].start<y&&R1[j].finish>=y){
				cout<<R1[j].era<<" "<<y-R1[j].start<<endl;
				f=true;
				break;
			}
			}
			if(f==false)cout<<"Unknown"<<endl;
			}
	}
return 0;
}

Measured memory_bytes: 1300
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    q,h,s,d=map(int,input().split())
    n=int(input())
    weight=[(0.25,q,q/0.25),(0.5,h,h/0.5),(1,s,s),(2,d,d/2)]
    weight.sort(key=itemgetter(2))
    cost=0
    for w in weight:
        kosu=n//w[0]
        cost+=int(w[1]*kosu)
        n-=w[0]*kosu
    print(cost)
if __name__=='__main__':
    main()

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


using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i+=1)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define repv(arr)  for(auto it=arr[i].begin();it!=arr[i].end();it++)  
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vl vector<long long int>
#define ssortA(arr)   stable_sort(arr.begin(),arr.end())
#define search(arr,c)  binary_search(arr.begin(),arr.end(),c)
#define pb   push_back
#define ll long long
#define LCM(a,b) boost::math::lcm(a,b)
#define cl_bf cin.ignore(numeric_limits<streamsize>::max(), '\n');

int main(){

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    vi arr(n);
    rep(i,0,n){
        cin>>arr[i];
    }
    ssortA(arr);
    int sum=0;
    rep(i,0,k){
        sum+=arr[i];
    }
    cout<<sum<<endl;
}



Measured memory_bytes: 3664
#include<iostream>
using namespace std;
int main() {
	long long int a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;

	if ((a % 2 == 0) || (b % 2 == 0) || (c % 2 == 0) ){
		cout << 0;
	}
	else {
		if ((a * b < a * c) && (a * b < b * c)) {
			cout << a * b;
		}
		else if (a * c < b * c) {
			cout << a * c;
		}
		else {
			cout << b * c;

		}
	}
	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  // Including tree_order_statistics_node_update

using namespace __gnu_pbds;
using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
#define minei(x) min_element(x.begin(), x.end()) - (x).begin()
#define maxei(x) max_element(x.begin(), x.end()) - (x).begin()
#define LSOne(S) (S & (-S))

#define uns(v) sort((v).begin(), (v).end()), v.erase(unique(v.begin(), v.end()), v.end())
#define acusum(x) accumulate(x.begin(), x.end(), 0)
#define acumul(x) accumulate(x.begin(), x.end(), 1, multiplies<int>());
#define bits(x) __builtin_popcount(x)
#define oo INT_MAX
#define inf 1000000000
#define MAXN 1000007
#define MOD 1000000007

const double pi = acos(-1.0);
const double eps = 1e-11;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
vector<int> N,W,E,S;
int Findpre(vector<int> &A,int x)
{
	if(!A.size())return 1;
	int l=0,r=A.size()-1,ret=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(A[mid]<=x)ret=mid,l=mid+1;
		else r=mid-1;
	}
	return A[ret];
}
int Findsuf(vector<int> &A,int x)
{
	if(!A.size())return 1;
	int l=0,r=A.size()-1,ret=r;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(A[mid]>=x)ret=mid,r=mid-1;
		else l=mid+1;
	}
	return A[ret];
}
int n,m,Q;char dS[100100],dT[100100];
struct Line{int v,next,w;}e[1000];
int bh[20][20],tot;
int h[100],cnt;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int dis[200];bool vis[200];
int SPFA(int S,int T)
{
	for(int i=1;i<=tot;++i)dis[i]=1e9,vis[i]=false;
	queue<int> Q;Q.push(S);dis[S]=0;vis[S]=true;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=h[u];i;i=e[i].next)
			if(dis[e[i].v]>dis[u]+e[i].w)
			{
				dis[e[i].v]=dis[u]+e[i].w;
				if(!vis[e[i].v])vis[e[i].v]=true,Q.push(e[i].v);
			}
		vis[u]=false;
	}
	return dis[T]<1e9?dis[T]:-1;
}
int main()
{
	n=read();m=read();Q=read();
	scanf("%s",dS+1);scanf("%s",dT+1);
	for(int i=1;i<=n;++i)
		if(dS[i]=='E')E.push_back(i);
		else W.push_back(i);
	for(int i=1;i<=m;++i)
		if(dT[i]=='N')N.push_back(i);
		else S.push_back(i);
	while(Q--)
	{
		int a=read(),b=read(),c=read(),d=read();
		vector<int> X,Y;
		X.push_back(Findpre(E,a));X.push_back(Findpre(W,a));
		X.push_back(Findsuf(E,a));X.push_back(Findsuf(W,a));
		X.push_back(Findpre(E,c));X.push_back(Findpre(W,c));
		X.push_back(Findsuf(E,c));X.push_back(Findsuf(W,c));
		Y.push_back(Findpre(N,b));Y.push_back(Findpre(S,b));
		Y.push_back(Findsuf(N,b));Y.push_back(Findsuf(S,b));
		Y.push_back(Findpre(N,d));Y.push_back(Findpre(S,d));
		Y.push_back(Findsuf(N,d));Y.push_back(Findsuf(S,d));
		sort(X.begin(),X.end());X.resize(unique(X.begin(),X.end())-X.begin());
		sort(Y.begin(),Y.end());Y.resize(unique(Y.begin(),Y.end())-Y.begin());
		int lx=X.size(),ly=Y.size(),S,T;tot=0;
		for(int i=0;i<lx;++i)
			for(int j=0;j<ly;++j)
			{
				bh[i][j]=++tot;
				if(X[i]==a&&Y[j]==b)S=tot;
				if(X[i]==c&&Y[j]==d)T=tot;
			}
		for(int i=1;i<=tot;++i)h[i]=0;cnt=2;
		for(int i=0;i<lx;++i)
			if(dS[X[i]]=='E')for(int j=0;j<ly-1;++j)Add(bh[i][j],bh[i][j+1],Y[j+1]-Y[j]);
			else for(int j=1;j<ly;++j)Add(bh[i][j],bh[i][j-1],Y[j]-Y[j-1]);
		for(int i=0;i<ly;++i)
			if(dT[Y[i]]=='N')for(int j=1;j<lx;++j)Add(bh[j][i],bh[j-1][i],X[j]-X[j-1]);
			else for(int j=0;j<lx-1;++j)Add(bh[j][i],bh[j+1][i],X[j+1]-X[j]);
		printf("%d\n",SPFA(S,T));
	}
}


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

int main() {
  int M;
  cin >> M;
  string S;
  cin >> S;
  if (S.size() <= M) {
    cout << S <<endl;
  }
  else {
    for (int i = 0; i < M; i++) {
      cout << S.at(i);
    }
    cout <<"..." <<endl;
  }
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include<algorithm>
#include<functional>
using namespace std;

int main()
{ 
	string s, t;
	cin >> s;
	cin >> t;
	sort(s.begin(), s.end());
	sort(t.rbegin(), t.rend());
	if (s < t)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 2005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,A,B;

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    read(N);read(A);read(B);
    int t = abs(B - A - 1);
    if(t & 1) puts("Alice");
    else puts("Borys");
    return 0;
}


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

int main() {
    int n, m;
    int t[100];
    int p[100];
    int x[100];
    
    cin >> n;
    rep(i, n) cin >> t[i];
    cin >> m;
    rep(i, m) {
        cin >> p[i] >> x[i];
        p[i]--;
    }
    
    rep(i, m) {
        int tt = 0;
        
        rep(ii, n) {
            if (p[i] == ii) {
                tt += x[i];
            }
            else {
                tt += t[ii];
            }
        }
        
        cout << tt << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
/*
g++ -std=c++14 -O2 -Wall a.cpp -o a && a
*/

//  io
#include <iostream>
//#include <fstream> //http://www.cplusplus.com/reference/fstream/fstream/
//#include <cstdio>
#include <iomanip> //http://www.cplusplus.com/reference/iomanip/
#include <limits>
//  util
#include <string>
#include <cstring>
#include <algorithm>
//#include <utility>
//#include <functional> //http://www.cplusplus.com/reference/functional/
//#include <cstdlib>
//#include <cmath>
//#include <complex>
//#include <random>
//#include <bitset>
//  containers https://en.cppreference.com/w/cpp/container
#include <vector>
//#include <queue>
//#include <set>
//#include <map>
//#include <unordered_set>
//#include <unordered_map>
//  time
//#include <ctime>
//#include <chrono>
//                  https://en.cppreference.com/w/cpp/header/chrono
//                  http://www.cplusplus.com/reference/chrono/

using namespace std;
typedef vector<int> arri;
typedef vector<float> arrf;
typedef pair<int, int> pairi;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 0x7fffffffffffffff;
const ll infneg = -0x7fffffffffffffff;

//int modadd(int a, int b) { return ((a += b) < mod) ? a : (a - mod); }
//int modmult(int a, int b) { return (int)((a * b) % mod) }

//file input routed to stdinout
/*
std::ifstream inFile("input.txt");
std::ofstream outFile("output.txt");
std::cin.rdbuf(inFile.rdbuf());
std::cout.rdbuf(outFile.rdbuf());
*/

vector<pair<vector<int>, int>> tree; //connections, value;

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

    int n, q;
    cin >> n >> q;

    tree.resize(n);

    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        tree[u - 1].first.push_back(v - 1);

        tree[u - 1].second = 0;
        tree[v - 1].second = 0;
    }
    for (int i = 0; i < q; i++)
    {
        int u, aux;
        cin >> u >> aux;
        tree[u - 1].second += aux;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < tree[i].first.size(); j++)
        {
            tree[tree[i].first[j]].second += tree[i].second;
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << tree[i].second << " ";
    }
}

Measured memory_bytes: 14976
import java.util.*;
public class Main {

		static void solve() {
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int res = 0;
			sc.close();
			for(int i = 1;i<=n;i++) {
				String s =String.valueOf(i);
				if(s.length()%2!=0){
					res++;
				}
			}
			System.out.println(res);
		}
	public static void main(String[] args) {
		solve();

	}

}


Measured memory_bytes: 28116
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define fop(i,m,n) for (int i=(m);i<(n);i++)
#define FOP(i,m,n) for (int i=(m)-1;i>=(n);--i)
#define test(x) cout << #x << ' ' << x << endl;
#define eb emplace_back
#define pb push_back
#define mp make_pair 
#define pii pair<int,int>
#define pli pair<lli,int> 
#define X first
#define Y second
const long long MOD = 1e9 + 7;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int d, n;
    cin >> s >> d;
    n = s.length();
    lli dp[n][d];
    fop (i,0,n) fop (j,0,d) dp[i][j] = 0;
    dp[0][0] = 1;
    fop (i,1,n) {
        fop (j,0,10) {
            fop (k,0,d) {
                int t = (k - j) % d;
                if (t < 0) t += d;
                dp[i][k] += dp[i - 1][t];
                if (dp[i][k] >= MOD) dp[i][k] -= MOD;
            }
        }
    }
    lli ans = 0;
    int now = 0;
    fop (i,0,n) {
        fop (j,0,s[i]-'0') {
            int t = (- now - j) % d;
            if (t < 0) t += d;
            ans += dp[n - i - 1][t];
            if (ans >= MOD) ans -= MOD;
        }
        now += (s[i] - '0');
    }
    now %= d;
    ans--;
    if (now == 0) ans++;
    ans %= MOD;
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
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 (b<a) { a=b; return 1; } return 0; }
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll INF = 1LL<<58;
 
int main(){
    ll N,M;
  	cin >> N >> M;
  	vector <ll> A(N);
  	vector <ll> B(N);
   	vector<pair<ll, ll> > pairs(N);
  	ll sum = 0;
  for(ll i = 0; i < A.size(); ++i) {
    cin >> A[i];
    cin >> B[i];
    pairs[i] = mp(A[i],B[i]);
  }
  sort(pairs.begin(), pairs.end());
  	for(ll i = 0; i < A.size(); ++i){
      if(pairs[i].second >= M){
        sum += M * pairs[i].first;
        cout << sum << endl;
        return 0;
      }
      else{
        sum += pairs[i].first * pairs[i].second;
        M -= pairs[i].second;
      }
    }
  	cout << sum << endl;
  
}

Measured memory_bytes: 3328
/*
 Templatka c++ Kacper Fis																							   																											   //
*/

#include <iostream>
#include <cstdio>
#include <limits>
#include <cstdlib>
#include <utility>
#include <iterator>
#include <bitset>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>
#include <time.h>
#include <iomanip>
#include <sstream>

using namespace std;

const int INF =  1000000001;
const float PI = 3.14;
typedef long long LL;

typedef vector<int> vi;
typedef list<int> li;
typedef queue<int> qi;
typedef pair<int,int> ii;
typedef map<string,int> msi; //np msi['nazwa'] = 'liczba'
typedef vector<ii> vii; //vector par<int>, do tworzenia tablicy dla grafów wagowych #dijkstra #Bellman_Ford
typedef priority_queue< ii, vector<ii>, greater<ii> > pq; //kolejka priorytetowa vectorów par(top()=min) #dijkstra

list<int>::iterator it;
list<int>::iterator it1;
vector<int>::iterator it2;
vector<int>::iterator it3;
set<int>::iterator it4;
map<string, int>::iterator it5;
vector<ii>::iterator iter;

#define print_list(x) for(it = (x).begin(); it != (x).end(); it++) {cout << *it << " ";}
#define print_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++) {cout << *it2 << " ";}
#define search_list(x) for(it = (x).begin(); it != (x).end(); it++)
#define search_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++);
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x, y) make_pair(x, y)
///////////////////////////////////////////////GLOBAL DEFINITIONS////////////////////////////////////////////////////////



///////////////////////////////////////////////////FUNCTIONS/////////////////////////////////////////////////////////////



/////////////////////////////////////////////////////MAIN////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	int n;
	cin >> n;

	vector< vector<char> >data;

	for(int i = 0; i < n; i++)
    {
        vector<char> cur(10);
        for(int i = 0; i < 10; i++)
            cin >> cur[i];
        sort(cur.begin(), cur.end());
        data.pb(cur);
    }

    sort(data.begin(), data.end());
    LL ans = 0;
    int start = 0;
    for(int i = 1; i < n; i++)
    {
       // cout << "i: " << i << endl;
        if(data[start] != data[i])
        {
            LL dif = i - start;
           // cout << "dif: " << dif << endl;
            ans += dif * (dif-1) /2;
            //cout << "ans: " << ans << endl;
            start = i;
           //cout << "start: " << start << endl;
        }
        //cout << endl;
    }

    LL dif = n - start;
    ans += dif * (dif-1) /2;

    cout << ans << endl;



	return 0;
}


Measured memory_bytes: 6836
X = int(input())
import math 
  
# Function that returns True if n  
# is prime else returns False  
def isPrime(n): 
      
    # Corner cases  
    if(n <= 1): 
        return False
    if(n <= 3): 
        return True
      
    # This is checked so that we can skip  
    # middle five numbers in below loop  
    if(n % 2 == 0 or n % 3 == 0): 
        return False
      
    for i in range(5,int(math.sqrt(n) + 1), 6):  
        if(n % i == 0 or n % (i + 2) == 0): 
            return False
      
    return True
  
if isPrime(X):
    print(X)
    exit()
# Function to return the smallest  
# prime number greater than N  
def nextPrime(N): 
  
    # Base case  
    if (N <= 1): 
        return 2
  
    prime = N 
    found = False
  
    # Loop continuously until isPrime returns  
    # True for a number greater than n  
    while(not found): 
        prime = prime + 1
  
        if(isPrime(prime) == True): 
            found = True
  
    return prime 

print(nextPrime(X)) 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pll = pair<long long,long long>;
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
//以上テンプレ

int main(){
    string S;
    cin>>S;
    rep(i,S.size()-1){
        if(S.at(i)=='A'&&S.at(i+1)=='C'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

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

int main(){
    string s; cin>>s;
    
    while(true){
        s.pop_back();
        s.pop_back();
        if(s.substr(0,s.length()/2)==s.substr(s.length()/2)){
            cout<<s.length()<<endl;
            return 0;
        }
    }
    
}

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

int main() {
    int64_t L,R;
    std::cin >> L >> R;
    
    int64_t mi = 2019;
    int64_t uplimit = std::min(R,L+1+2019);
    for(int64_t i = L; i <=(uplimit-1); ++i) {
        for(int64_t  j = L + 1; j <=uplimit; ++j) {
            mi = std::min(mi,(i*j)%2019);
            if(mi ==0) {
                std::cout << 0 << std::flush;
                return 0;
            }
        }
    }
    
    std::cout << mi << std::flush;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		do{
			int x = i;
			if(x%3 == 0){
				System.out.printf(" %d", i);
				continue;
			}
			do{
				if(x%10 == 3){
					System.out.printf(" %d", i);
					break;
				}
				x /= 10;
			}while(x > 0);
		}while( ++i <= n );
		System.out.printf("\n");
	}
}

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

int main() {
  int N, K;
  int ans = 1;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    if (ans > K) {
      ans += K;
    }
    else {
      ans *= 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
	int K, a, cnt = 0;
	scanf("%d", &K);

	a = K / 2;

	if (K % 2 == 1) {
		cnt = a*(a + 1);
	}
	else {
		cnt = a*a;
	}



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


Measured memory_bytes: 128
#include <iostream>
#include <string>
#define ll long long
using namespace std;
int main () {
    string N;
    ll M, cnt=0;;
    cin >> N >> M;
    for (int i=0; i<N.size();i++){
        if (N[i]!='1'){
            cnt=i;
            break;
        }
    }
    M<cnt+1 ? cout << N[M-1] : cout << N[cnt];
    return 0;
}

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

int main() {
  
  string S, T, nS;
  cin >> S >> T;
  int t;
  t = T.size();
  t--;
  char P;
  P = T.at(t);
  nS = S + P;
  if (T == nS){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	if((a <= c && c <= b) || (a >= c && c >= b))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3640
#include <stdio.h>

#define Max 1000

void  swap(int *x, int *y)
{
    int  buff;
	
	buff = *x;
	*x = *y;  
	*y = buff;
}

void insertionSort(int A[Max], int N) {
	int i, j, v;

	for (i = 0; i < N; i++) { 
		v = A[i];
		j = i - 1;
		while (j >= 0 && A[j] < v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
	}
}

void insertionSort4(int A[Max]) {
	int i, j, v;

	i = 3;
	v = A[i];
	j = i - 1;
	while (j >= 0 && A[j] < v) {
		A[j + 1] = A[j];
		j--;
	}
	A[j + 1] = v;
}

int main( ) {
	int N, i, count;
	int num[Max];
	int top[4];

	N = 10;

	for (i = 0; i < N; i++) scanf("%d", &num[i]);

	for (i = 0; i < 3; i++) top[i] = num[i];
	insertionSort(top, 3);

	for (i = 3; i < N; i++) {
		top[3] = num[i];
		insertionSort4(top);
	}

	for (i = 0; i < 3; i++)
		printf("%d\n", top[i]);

	return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

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

   	if(a == b)
   		cout << "Draw" << endl;
   	else if(a == 1)
   		cout << "Alice" << endl;
   	else if(b == 1)
   		cout << "Bob" << endl;
   	else
   	{
   		if(a > b)
   			cout << "Alice" << endl;
   		else
   			cout << "Bob" << endl;
   	}

}

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

#define BEFORE 0
#define AFTER 1

long int org_array[100001];
long int q_array[100001][2];
long int conver_array[100001];
long long int a_array[100001];

int main()
{
    long int n, q;
    long int max_num = 0;
    long long int sum = 0;

    scanf("%ld", &n);

    for (long int i = 0; i<n; i++)
    {
        scanf("%ld", &org_array[i]);

        if (org_array[i] > max_num)
        {
            max_num = org_array[i];
        }
    }

    scanf("%ld", &q);

    for (long int i = 0; i<q; i++)
    {
        scanf("%ld %ld", &q_array[i][BEFORE], &q_array[i][AFTER]);
    }

    for (long int i = 0; i<=100000; i++)
    {
        conver_array[i] = 0;
    }

    for (long int i = 0; i<n; i++)
    {
        conver_array[org_array[i]] ++;
    }

    for (long int i = 0; i<n; i++)
    {
        sum += org_array[i];
    }

    for (long int i = 0; i<q; i++)
    {
        long int move_index = 0;

        move_index = conver_array[q_array[i][BEFORE]];
        conver_array[q_array[i][AFTER]] += move_index;
        conver_array[q_array[i][BEFORE]] = 0;

        sum -= move_index*q_array[i][BEFORE];
        sum += move_index*q_array[i][AFTER];

        a_array[i] = sum;

    }

    for (int i = 0; i<q; i++)
    {
        printf("%lld\n", a_array[i]);
    }

    return 0;
}

Measured memory_bytes: 5548
V, E, r = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))

INF = 10**18
dist = [INF] * V
dist[r] = 0
update = 1
for _ in xrange(V):
    update = 0
    for v, e in enumerate(g):
        for t, cost in e:
            if dist[v]!=INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
    print "NEGATIVE CYCLE"
    exit(0)
for i in xrange(V):
    print dist[i] if dist[i]<INF else "INF"

Measured memory_bytes: 6560
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    int n, t, a;
    cin >> n;
    cin >> t >> a;
    vector<int> h(n);
    REP(i, n) cin >> h[i];
    
    int min_index = -1;
    double min_td = MAXR;
    REP(i, n) {
        double tmp = t - h[i]*0.006;
        if(min_td > abs(a-tmp)) {
            min_td = abs(a - tmp);
            min_index = i;
        }
    }
    cout << min_index+1 << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    temp = I()
    print("ACL"*temp)
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 9500
#include<bits/stdc++.h>
#define ll long long
#define inf 1e9
#define pii pair < int, int >
using namespace std;

int main()
{
    string s;

    cin >> s;

    if(s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


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

int cmpnum(const void * n1, const void * n2)
{
	if (*(long *)n1 > *(long *)n2)
	{
		return 1;
	}
	else if (*(long *)n1 < *(long *)n2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void) {

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  qsort(a, n, sizeof(long), cmpnum);
  long answer = 0;
  long number = a[0];
  long count = 0;
  for (long i = 0; i < n-1; i++) {
    count++;
    if (a[i+1] != number) {
      if (count < number) {
        answer += count;
      } else {
        answer += count-number;
      }
      number = a[i+1];
      count = 0;
    }
  }
  count++;
  if (count < number) {
    answer += count;
  } else {
    answer += count-number;
  }
  printf("%ld\n", answer);

  return 0;
}

Measured memory_bytes: 1660
using System;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] weekdays = { "", "SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN" };
            string s = Console.ReadLine();

            for(int i = 0; i < weekdays.Length; i++)
            {
                if(weekdays[i] == s)
                {
                    Console.WriteLine(i.ToString());
                }
            }
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13140
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;

vector<int> a;
int s;
int n;
int m;
int q;
int best;

const int N = 55;
int A[N], B[N], C[N], D[N];

int calc() {
        int res = 0;
        for (int i = 0; i < q; ++i) {
                if (a[B[i]] - a[A[i]] == C[i])
                        res += D[i];
        }
        return res;
}

void build() {
        if (a.size() == n) {
                best = max(best, calc());
                return;
        }
        int start = (a.size()) ? a.back() : 1;
        for (int i = start; i <= m; ++i) {
                a.push_back(i);
                build();
                a.pop_back();
        }
}

int main() {
        cin.sync_with_stdio(0);
       
        cin >> n >> m >> q;
        for (int i = 0; i < q; ++i) {
                cin >> A[i] >> B[i] >> C[i] >> D[i];
                --A[i], --B[i];
        }

        build();
        cout << best;

        return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <memory.h>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
typedef long long ll;

const int maxn = 5e3 + 5;

struct Node
{
    int h, p;
    bool operator<(const Node cmp) const
    {
        if (h + p < cmp.h + cmp.p)
            return true;
        if (h + p == cmp.h + cmp.p && h < cmp.h)
            return true;
        return false;
    }
} a[maxn];

int n;
ll dp[maxn]; //前i个人最少有多少块坐垫；
inline int read() 
{
    int w = 0, t = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            t = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        w = (w << 3) + (w << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w * t;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i].h =read(), a[i].p = read();
    std::sort(a + 1, a + n + 1);
    memset(dp, 0x3f, sizeof dp); //init
    ll inf = dp[0];
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j >= 1; j--)
            if (dp[j - 1] <= a[i].h)
                dp[j] = std::min(dp[j], dp[j - 1] + a[i].p); //dp[j] = (dp[j - 1] < h[i])min{dp[j - 1] + p}
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (dp[i] < inf) res = i;
        // printf("$%d %d\n", i, dp[i]);
    }
    printf("%d", res);
}

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

dp = [0 for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    if H[A-1] > H[B-1]:
        dp[B-1] = 1
    elif H[A-1] == H[B-1]:
        dp[A-1] = 1
        dp[B-1] = 1
    elif H[B-1] > H[A-1]:
        dp[A-1] = 1

cnt = 0
for i in dp:
    if i == 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 84992
#include <bits/stdc++.h>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

typedef long long ll;

using namespace std;

int main(){

    int n,k;
    cin >> n >> k;

    vector<int> p;

    rep(i,n){
        int tmp;
        cin >> tmp;
        p.pback(tmp);
    }

    int tmpsum = 0;
    int tmpmax = 0;

    rep(i,k){
        tmpsum += p[i] + 1;
    }

    tmpmax = tmpsum;

    for(int i = 1; i <= n - k; i++){
        tmpsum -= p[i - 1];
        tmpsum += p[i - 1 + k];

        if(tmpsum > tmpmax){
            tmpmax = tmpsum;
        }
    }

    cout << setprecision(12) << (double)tmpmax / 2 << endl;

    return 0;
}


Measured memory_bytes: 1400
n,y=map(int,input().split())

a,b,c=-1,-1,-1

for i in range(n+1):
  for j in range(n+1):
    h=n-i-j
    if 10000*i+5000*j+1000*h==y and h>=0:
      a,b,c=i,j,h
      break

print("{} {} {}".format(a,b,c))

Measured memory_bytes: 9108
import sys
import functools
import fractions

if __name__ == '__main__':
    NX = [int(n) for n in input().split()]
    X = [int(n) for n in input().split()]
    if len(X) == 1:
        print(abs(X[0]-NX[1]))
        sys.exit(0)

    X.append(NX[1])
    X.sort()
    diff = [X[i] - X[i-1] for i in range(1, len(X))]
    D = functools.reduce(fractions.gcd, diff)
    print(D)
    # D = min(diff)
    # while any(np.array(diff)%D):
    #     D -= 1
    # print(D)

Measured memory_bytes: 16304
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

#B = [bin(a)[2:].zfill(61)[::-1] for a in A]
N1 = []
for i in range(0,61):
    m = sum([a % 2 for a in A])
    N1.append(m)
    for j in range(N):
        A[j] = A[j] >> 1

ans = 0
for i,n1 in enumerate(N1):
    n0 = N-n1
    m = n0 * n1
    ans += 2**i * m
    ans = ans % MOD
print(ans % MOD)






Measured memory_bytes: 122808
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll n; cin >> n;
    vector<pll> xy(n);
    for(int i = 0; i < n; i++){
        cin >> xy[i].first >> xy[i].second;
    }
    sort(all(xy));

    map<pll, int> mp;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            pll diff = {xy[j].first - xy[i].first, xy[j].second - xy[i].second};
            mp[diff]++;
        }
    }
    int maxval = 0;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr){
        maxval = max(maxval, itr->second);
    }

    cout << n-maxval << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
 
#define pi 3.1415926535

int main()
{
  string s, t;

  cin >> s >> t;

  int n = s.size() - t.size() + 1;
  int max = 0, tmpMax = 0;
  for(int i = 0; i < n; i++){
    tmpMax = 0;
    for(int j = 0; j < t.size(); j++){
      if(t[j] == s[i + j]){
        tmpMax++;
      }
    }
    
    if(tmpMax > max){
      max = tmpMax;
    }
  }

  cout << t.size() - max << endl;

  return 0; 
}

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

using namespace std;

int main() {
  int n,k;
  cin>>n>>k;
  vector<int> x(n);
  rep(i,n)cin>>x[i];
  int ans=0;
  rep(i,n){
    if(x[i]<=k-x[i])ans+=x[i]*2;
    else ans+=(k-x[i])*2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

    Happy = [[0, 0, 0] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(3):
            for k in range(3):
                if j != k:
                    Happy[i][j] = max(Happy[i][j], Happy[i-1][k] + A[i-1][j])

    print(max(Happy[n]))
resolve()

Measured memory_bytes: 73948
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(x)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> T& chmin(T &a, const U &b){return a = (a<=b?a:b);}
template <typename T, typename U> T& chmax(T &a, const U &b){return a = (a>=b?a:b);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

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

  int a,b,c;  
  while(cin >> a >> b >> c){
    if(a==b and b==c)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
using ll = int64_t;
using P = pair<ll,ll>;
ll INF = 1000000007;
// ll INF = 9223372036854775807;
// ll INF = 998244353;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    ll n;
    cin >> n;
    string s = to_string(n);
    char c = s.at(s.size()-1);
    string res = "";
    if(c=='2' || c=='4' || c=='5' || c=='7' || c=='9') res = "hon";
    if(c=='0' || c=='1' || c=='6' || c=='8') res = "pon";
    if(c=='3') res = "bon";
    cout << res << endl;
}


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

int main() {

int n;
cin>>n;
vector<int>list(n);
rep(i,n-1)
{int a;
cin>>a;
list.at(a-1)++;}

rep(i,n)
{cout<<list.at(i)<<endl;}

return 0;

}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 3960
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main
{
  
  static int ks[] = {1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049};
  static int lm[] = {0, 2, 4,  4,  8,   8,   16,  16,   32,   32,    64,    64};
  static int mem[][] = new int[100001][12];

  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    int n = Integer.parseInt(r.readLine());
    
    Arrays.sort(ks);
    int ans = search(n, 11);

    System.out.println(ans);

  }
  
  public static int search(int m, int k)
  {
    if(m <= 5)
    {
      return m;
    }
    if(k < 0)
    {
      return 999999;
    }
    if(mem[m][k] > 0)
    {
      return mem[m][k];
    }
    int z = 999999;
    int v = m;
    for(int i = 0; m >= 0 && i < lm[k]; i++)
    {
      z = Math.min(z, i + search(m, k - 1));
      m -= ks[k];
    }
    mem[v][k] = z;
    return z;
  }

}


Measured memory_bytes: 28884
from collections import deque
n, d, a = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort()
d *= 2
ans, tot = 0, 0
q = deque()
for x, h in p:
    while (q and q[0][0] < x):
        tot -= q[0][1]
        q.popleft()
    h -= tot
    if h>0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        tot += damage
        q.append((x+d, damage))
print(ans)


Measured memory_bytes: 66368
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<string>s(n);
	for(int i=0;i<n;i++){
		cin>>s.at(i);
		for(int j=0;j<i;j++){
			if(s.at(j)==s.at(i)){
				cout<<"No"<<endl;
				return 0;
			}
		}
		if(i==0)continue;
		string t=s.at(i-1),u=s.at(i);
		if(t.at(t.size()-1)==u.at(0))continue;
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
}

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

int main(){
  int64_t N;
  cin>>N;
  int64_t sum=0;
  for(int i=1;i<=N;++i){
    if(i%3!=0 && i%5!=0) sum += i;
  }
  cout<<sum<<endl;
}


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

int main() {
    ios::sync_with_stdio(false); 
    int n; cin >> n; 
    vector<int> a(20, 0); 
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i]; 
    }
    int ans = 0; 
    for (int i = 1; i <= n-2; i++) {
        if (a[i-1] > a[i] and a[i+1] < a[i]) ans++; 
        else if (a[i+1] > a[i] and a[i-1] < a[i]) ans++;
    }

    cout << ans << "\n"; 

    
}

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

using namespace std;

int main(void)
{
  int n, p;
  
  while(cin >> n >> p){
    if(n == 0 && p == 0) break;
    
    vector<int> array(n, 0);
    int m = p;
    
    int index = 1;
      while(1){
	
	if(p > 0){
	  array[index]++;
	  p--;
	  if(array[index] == m) break;
	}else{
	  p += array[index];
	  array[index] = 0;
	}
	if(index == n-1) index = 0;
	else index++;
      }
    if(index == 0) cout << n - 1 << endl;
    else cout << index - 1 << endl;
  }  
  
  return 0;
}

  

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

// DAME:
int main() {
	int N;
	cin >> N;
	vector<int> x(N), y(N), h(N);
	for (int i = 0; i < N; i++)
	{
		cin >> x[i] >> y[i] >> h[i];
	}

	//[0, 100]に座標があるのでMAXを定義すると楽
	int MAX = 100;

	for (int posY = 0; posY <= MAX; posY++)
	{
		for (int posX = 0; posX <= MAX; posX++)
		{
			//頂上がどれくらいの高さであってほしいか。
			//-1はまだ良く分からない時。0以上は確定してるとき
			//-2はダメだって分かった時
			int needH = -1;

			for (int i = 0; i < N; i++)
			{
				if (h[i] > 0) {
					//この頂点から見て、頂上がposY,posXの時に、
					//どれくらいの高さがあってほしいかを求める
					int tmp = h[i] + abs(posY - y[i]) + abs(posX - x[i]);
					if (needH == -1) {
						needH = tmp;
					}
					else {
						if (needH != tmp) {
							needH = -2;
							break;
						}
					}
				}
			}
			//ダメだったら別の場所を探す。
			if (needH == -2) continue;

			for (int i = 0; i < N; i++)
			{
				//高さが0の場合に矛盾してないか調べる
				if (h[i] == 0) {
					int dist = abs(posY - y[i]) + abs(posX - x[i]);
					if (needH > dist) {
						needH = -2;
						break;
					}
				}
			}

			if (needH == -2) continue;

			//見つけられたら答えをそのまま返す。
			cout << posX << " " << posY << " " << needH << endl;
			return 0;
		}
	}

}






Measured memory_bytes: 256
h,w = map(int,input().split())
l = [['*']*(w+2)]
for i in range(h):
    l.append(['*']+list(input())+['*'])
l.append(['*']*(w+2))


for i in range(1,h+1):
    s = ''
    for j in range(1,w+1):
        directions = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
        alist = [(i+dir[0],j+dir[1]) for dir in directions]
        cnt = 0
        for a in alist:
            if l[a[0]][a[1]] == '#':
                cnt += 1
        if l[i][j] == '#':
            s += '#'
        else:
            s += str(cnt)
    print(s)

Measured memory_bytes: 68356