akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) std::cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) std::cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) std::cout << x << endl;
#define println(x) std::cout << x << endl;
using namespace std;
// using namespace atcoder;

template<typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

bool check(vector<ll> v, ll target, bool xmode) {
    ll sum = accumulate(all(v), 0LL);

    vector<vector<int> > dp(v.size() + 1, vector<int>(2 * sum + 1));
    dp[0][0 + sum] = 1;

    rep(i, v.size()) {
        rep(j, dp[i].size()) {
            if (j + v[i] < dp[i+1].size()){
                chmax(dp[i+1][j + v[i]], dp[i][j]);
            }
            if (xmode && i == 0) {
                // 初回は絶対にX軸正の方向にしか動けない！！
                continue;
            }
            if (j - v[i] >= 0) {
                chmax(dp[i+1][j - v[i]], dp[i][j]);
            }
        }
    }

    if (target + sum < 0 || dp[0].size() <= target + sum) {
        return false;
    }

    ll res = dp[v.size()][target + sum];
    return res > 0;
}

void Main()
{
    string s;
    cin >> s;

    ll x, y;
    cin >> x >> y;

    vector<ll> dx, dy;
    bool flg = false;
    ll delta = 0;
    rep(i, s.size()) {
        if (s[i] == 'T') {
            if (flg == false) {
                dx.push_back(delta);
            }
            else {
                dy.push_back(delta);
            }
            flg = !flg;
            delta = 0;
        }
        else {
            delta++;
        }
    }

    if (flg == false) {
        dx.push_back(delta);
    }
    else {
        dy.push_back(delta);
    }

    bool res = check(dx, x, true) && check(dy, y, false);
    yorn(res);

}
signed main(){ Main();return 0;}

Measured memory_bytes: 66004
s=list(input())
t=list(input())
for i in range(len(s)-len(t),-1, -1):
    for j in range(len(t)):
        if not (s[i+j] == t[j] or s[i+j] == '?'):
            break
    else:
        s[i:i+len(t)] = t
        for i in range(len(s)):
            if s[i] == '?':
                s[i] = 'a'
        print(''.join(s))     
        break
else:
    print('UNRESTORABLE')


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

int r, g, b;

int main(void){
	
	scanf("%d %d %d", &r, &g, &b);
	
	if((r * 100 + g * 10 + b) % 4 == 0) printf("YES\n");
	else printf("NO\n");
	
    return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



int n, a[111],b[111],h[111];
void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i] >> h[i];
	}
	
	for(int i = 0; i <= 100; i++){
		for(int j = 0; j <= 100; j++){
			int H = 0;
			for(int k = 0; k < n; k++){
				if(h[k] == 0) continue;
				H = h[k]+abs(a[k]-i)+abs(b[k]-j);
				break;
			}
			bool ok = 0;
			for(int k = 0; k < n; k++){
				if(H == h[k]+abs(a[k]-i)+abs(b[k]-j)) continue;
				if(h[k] == 0 && H <= abs(a[k]-i)+abs(b[k]-j)) continue;
				ok = 1;
				break;
			}
			if(ok) continue;
			cout << i << " " << j << " " << H << endl;
			return;
		}
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N, L, Lp = 0, S = 0;

  std::cin >> N;

  for (int i = 0; i < N; i ++) {
    std::cin >> L;

    Lp = std::max(L, Lp);

    S += L;
  }

  std::cout << (Lp < S - Lp ? "Yes" : "No") << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
import sys

lines = sys.stdin.readlines()

strings = []
for n, line in enumerate(lines):
  if n == 0:
    N, L = [int(_) for _ in line.strip().split(' ')]
    continue
  strings.append(line.strip())

def append(source, target):
  source = sorted(source)
  target.append(source[0])
  source.remove(source[0])
  if not len(source):
    return ''.join(target)
  return append(source, target)
  
print(append(strings, []))

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

int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    int a,b;
    cin >> a >> b;
    while(a-b>0)
      a=a-b;
    cout << a << endl;
  }
  return 0;
}

Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define file_se_input  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pp long long int
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define eb emplace_back
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned long long int
#define test int t;cin>>t; while(t--)
#define um unordered_map
#define en '\n'
#define us unordered_set
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007


bool check_prime(long long n)
{
	int flag = 0;
	for (long long i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			flag = 1;
			break;
		}
	}
	if (n == 1)
		return false;
	else if (flag == 0 || n == 2 || n == 3)
	{
		return true;
	}
	else
	{
		return false;
	}

}

int BE(int x, int n, int m) //function to calculate x raise to power n modulo m
{
	int result = 1;
	while (n > 0)
	{
		if (n % 2 == 1)
			result = result * x % m;
		x = x * x % m;
		n = n / 2;
	}
	return result;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________

	int n;
	cin >> n;
	int a[n];
	zip(i, 0, n)
	{
		cin >> a[i];
	}
	int pre[n];
	int pre2[n];
	pre[0] = a[0];
	pre2[0] = a[0];
	zip(i, 1, n)
	pre[i] = pre[i - 1] + a[i], pre2[i] = pre2[i - 1] + a[i];
	//Try two possibilities independently: even-length prefixes are positive
	//or odd-length prefixes are positive
	int ans1 = 0;
	/* case 1 :- if(i is even then sum should be positive...)*/
	int var = 0;
	zip(i, 0, n)
	{
		pre[i] = pre[i] + var;
		if (i % 2 == 0)
		{
			if (pre[i] <= 0)
			{
				ans1 += -1 * pre[i] + 1;
				var += -1 * pre[i] + 1;
				pre[i] = 1;


			}
		}
		else
		{
			if (pre[i] >= 0)
			{
				ans1 += pre[i] + 1;
				var -= (pre[i] + 1);
				pre[i] = -1;

			}
		}
	}
	/* case 2 :- if i is even sum should be negative...)*/
	int ans2 = 0;
	var = 0;
	zip(i, 0, n)
	{
		pre2[i] = pre2[i] + var;
		if (i % 2)
		{
			if (pre2[i] <= 0)
			{
				ans2 += -1 * pre2[i] + 1;
				var += -1 * pre2[i] + 1;
				pre2[i] = 1;

			}
		}
		else
		{
			if (pre2[i] >= 0)
			{
				ans2 += pre2[i] + 1;
				var -= (pre2[i] + 1);
				pre2[i] = -1;


			}
		}
	}
	//cout << ans1 << en << ans2 << en;
	int ans = min(ans1, ans2);
	cout << ans << en;
	return 0;
}



Measured memory_bytes: 5924
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin>>a;
	char op;
	cin>>op;
	int b;
	cin>>b;
	switch(op){
		case '+':
		cout<<a+b;
		break;
		case'-':
		cout<<a-b;
		break;
	}
	return 0;
}

Measured memory_bytes: 256
def main():
    a = int(input())
    ans = ''

    for i in range(1, 99):
        if a <= 26 ** i:
            a -= 1
            for j in range(i):
                ans += chr(ord('a') + a % 26)
                a //= 26
            break
        else:
            a -= 26 ** i
    print(ans[::-1])


if __name__ == "__main__":
    main()

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define For(i,l,r)for(res i=(l),_=(r);i<=_;++i)
#define Dor(i,l,r)for(res i=(r),_=(l);i>=_;--i)
#define Sor(i,l,r)for(res i=(l),_=(r);i<_;++i)
#define ll long long
#define fz(a,b)memset(a,b,sizeof a)
#define N 200001
#define M 1000000007
int main() {
	int a,b;
	cin>>a>>b;
	For(i,b-a+1,b+a-1)cout<<i<<" ";
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
int main()
{
	int n;
	cin>>n;
	queue<ll> q;

	for(int i=1;i<=9;i++)
	{
		q.push(i);
	}

	ll ans;

	while(!q.empty())
	{
		ll num=q.front();
		q.pop();
		n--;
		if(n==0)
		{
			ans=num;
			break;
		}

		ll rem=num%10;

		if(rem==0)
		{
			q.push(10*num);
			q.push(10*num+1);
		}
		else if(rem==9)
		{
			q.push(10*num+8);
			q.push(10*num+9);
		}

		else
		{
			q.push(10*num+rem-1);
			q.push(10*num+rem);
			q.push(10*num+rem+1);
		}

	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 5180
#include<bits/stdc++.h>
using namespace std;
//const int N=
typedef long long LL;
map<string,bool>a;
string s;
int n,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s;
		if(!a[s])a[s]=1,ans++;
	}
	cout<<ans<<endl;
} 

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,k;
	cin >> n >> k;
	int a[n];
	for(int i=0; i<n; i++)cin >> a[i];
	sort(a,a+n);
	int sum=0;
	for(int i=0; i<k; i++)sum+=a[i];
	cout << sum;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 3660
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;

int arr[101] = {0};

int main()
{
	int a, total2=9999999;
	cin >> a;
	for(int i=0; i<a; i++)
	{
		cin >> arr[i];
	}
	for(int i=0; i<=100; i++)
	{
		int total=0;
		for(int j=0; j<a; j++)
		{
			total += (arr[j]-i)*(arr[j]-i);
		}
		if(total < total2)
		{
			total2=total;	
		}
	}
	cout << total2;
}



Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef pair< int , int > Pi;

int main(){
  int N, M;

  cin >> N >> M;

  int s, t, e;
  vector< vector< Pi > > data(N);
  while(cin >> s >> t >> e, s){
    data[--s].push_back( make_pair( --t, e));
  }

  int L;
  cin >> L;
  while(L--){
    vector< int > b(M);
    for(int i = 0; i < M; i++){
      cin >> b[i];
    }
    for(int i = 0; i < N; i++){
      int ret = 0;
      for(int j = 0; j < data[i].size(); j++){
        ret += b[data[i][j].first] * data[i][j].second;
      }
      cout << (i == 0 ? "": " ") << ret;
    }
    cout << endl;
  }
}

Measured memory_bytes: 2252
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
string s[100010];
int tab[100000][26]={};
int skip[100000]={};

int main(){
    int N;
    cin >> N;
    rep(i,N){
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }
    unordered_map<string, int> dict;
    long long cnt=0;
    int c=0;
    rep(i,N){
        cnt += dict[s[i]];
        dict[s[i]]++;
        
    }
    cout << cnt << endl;
}

Measured memory_bytes: 17700
n, x = map(int,input().split())
City = list(map(int, input().split()))
Distance = [0] * n

for i in range(n):
    Distance[i] = abs(City[i]-x)

Distance.sort()
ans = Distance[0]

def gcd(a,b):
    if a < b:
        a,b = b,a
    while a % b != 0:
        a, b = b, a % b
    return b

for i in range(1,n):
    ans = gcd(ans, Distance[i])

print(ans)


Measured memory_bytes: 62576
import re
ab = list(map(int, input().split()))
S = input()
if S[ab[0]] != '-':
    print("No")
    exit()

s = S.split('-')
if len(s) > 2:
    print("No")
    exit()

for i in range(2):
    if not ( len(s[i]) == ab[i] and re.compile(r'\d').match(s[i]) ):
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3188
import java.util.Scanner;

/*
 * AtCoder Beginner Contest 100 C
 */
public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int N = scanner.nextInt();

		int count_even = 0;
		for (int i = 0; i < N; i++) {
			int a = scanner.nextInt();
			while (a % 2 == 0) {
				a /= 2;
				count_even++;
			}
		}

		System.out.println(count_even);

	}

}

Measured memory_bytes: 34948
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)
vector<vector<int>> G;
vector<bool> seen;
vector<pair<int, int>> edge;
void dfs(int now, int parent, int except)
{
    seen[now] = true;
    // cout << "except: " << edge[except].first << " " << edge[except].second << endl;
    for (int child : G[now])
    {
        // cout << "next: " << now << " " << child << endl;
        if (now == edge[except].first && child == edge[except].second)
            continue;
        if (child == edge[except].first && now == edge[except].second)
            continue;
        if (seen[child])
            continue;
        if (child == parent)
            continue;
        dfs(child, now, except);
    }
    return;
}
int main()
{
    int n, m;
    cin >> n >> m;
    G.resize(n, vector<int>());
    repi(i, m, 0)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edge.push_back({a, b});
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = 0;
    seen.resize(n, false);

    repi(i, m, 0)
    {
        seen.assign(n, false);
        dfs(0, -1, i);
        // cout << i << " : ";
        repi(j, n, 0)
        {
            // cout << seen[j] << " ";
            if (!seen[j])
            {
                ans++;
                break;
            }
        }
        // cout << endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define RI(a) scanf("%d",&a)
#define RII(a,b) scanf("%d%d",&a,&b)
#define RIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;

int cnt[26]={0};
int main()
{
	int n,m;
	cin>>n>>m;
	REP(i,n) REP(j,m){
		char a;
		cin>>a;
		cnt[a-'a']++;
	}
	int type[3]={0};
	for(int i=0;i<26;i++){
		if(cnt[i]%2) type[0]++;
		else if(cnt[i]%4) type[1]++;
		else type[2]++;
	}
	
	if(n*m%2){
		if(type[0]!=1){
			puts("No");
			return 0;
		}
		if(type[1]>(n+m-2)/2){
			puts("No");
			return 0;
		}
		puts("Yes");
		return 0;
	}
	else if((n+m)%2){
		if(type[0]){
			puts("No");
			return 0;
		}
		int tmp=(n%2)?m/2:n/2;
		if(type[1]>tmp){
			puts("No");
			return 0;
		}
		puts("Yes");
		return 0;
	}
	else{
		if(type[0]){
			puts("No");
			return 0;
		}
		if(type[1]){
			puts("No");
			return 0;
		}
		puts("Yes");
		return 0;
	}
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7
def intread():
    return int(sysread())
def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def run():
    N, K = mapline()
    inv = generate_inv(K, mod)
    cache1 = 1
    cache2 = 1
    for i in range(1, K+1):
        cache1 *= (N-K+1 - (i-1))
        cache1 %= mod
        cache1 *= inv[i]
        cache1 %= mod
        if i == 1:
            cache2 = 1
        else:
            cache2 *= K-1 - (i-2)
            if cache2 == 0:
                cache2 = 1
            else:
                cache2 %=mod
                cache2 *= inv[i-1]
                cache2 %= mod
        #print(cache1, cache2)
        print(cache1 * cache2 % mod)



if __name__ == "__main__":
    run()


Measured memory_bytes: 9236
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int r,c;
int maze[15][10005];
int maxRes;

void rev(int n){
    for(int i=0;i<c;i++){
        maze[n][i]=maze[n][i]^1;
    }
}

int cal(){
    int sum=0;
    for(int j=0;j<c;j++){
        int cou1=0;
        for(int i=0;i<r;i++){
            cou1+=maze[i][j]; //统计1的个数
        }
        sum+=max(cou1,r-cou1);
    }
    return sum;
}

void dfs(int n){
    if(n==r){
        maxRes=max(maxRes,cal());
        return;
    }
    rev(n);
    dfs(n+1);
    rev(n);
    dfs(n+1);
}

void solve(){
    scanf("%d%d",&r,&c);
    while(r!=0||c!=0){
        maxRes=0;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                scanf("%d",&maze[i][j]);
            }
        }
        dfs(0);
        printf("%d\n",maxRes);
        scanf("%d%d",&r,&c);
    }
}

int main(){
    solve();
    return 0;
}


Measured memory_bytes: 3484
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(cont) cont.begin(), cont.end()
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef set<int> si;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<int, pair<int, int>> pipii;
 
const int INF = 1e9+1;
const int MAX_N = 1e5+1;
const int mod = 1000000007;
 
const double PI = acos(-1);
const double halfC = PI / 180;


int dp[MAX_N][3] = {0};
void solve(){
	int n;
	cin >> n;
	
	vi h[n];
	int a, b, c;
	for(int i =0; i < n; ++i){
		cin >> a >> b >> c;
		h[i].pb(a); h[i].pb(b); h[i].pb(c);
	}
	dp[0][0] = h[0][0];
	dp[0][1] = h[0][1];
	dp[0][2] = h[0][2];
	
	for(int i = 1; i < n; ++i){
		dp[i][0] = max(dp[i-1][1], dp[i-1][2])+h[i][0];
		dp[i][1] = max(dp[i-1][0], dp[i-1][2])+h[i][1]; 
		dp[i][2] = max(dp[i-1][0], dp[i-1][1])+h[i][2]; 
	}
	
	cout << max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
	
}
 
int main(){
	//freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int i = 1, t = 1;
	//cin >> t;
	while(i <= t){
		//cout << "CASE #" << i << ": ";
		solve();
		i++;
	}	
	return 0;
}

Measured memory_bytes: 6912
#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a, int b){
    if (b==0) return a;
    a%=b;
    return gcd(b, a);
}
int main(){
    int a,b;
    while (cin >> a >> b){
        int d;
        d = gcd(a,b);
        long e;
        e = a*(b/d);
        cout << d << " " << e <<  endl;
    }
}



Measured memory_bytes: 3084
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

//void substring_dfs(vector < int, int > substring){
    
//}


int main(int argc, const char * argv[]) {
    // insert code here...
    
    int temp;
    int max = 0;
    int result = 0;
    int k = 0;
    
    for(int i = 0; i < 3; i++){
        cin >> temp;
        if (max < temp) max = temp;
        result += temp;
    }
    result -= max;
    
    cin >> k;
    for(int i=0; i < k; i++){
        
        max *= 2;
        
    }
    result += max;
    
    cout << result << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int main(){
    int n, k; cin >> n>> k;
    ll ans = 0;
    FOR(i,k+1, n+1){
        ans += n/i * (i-k);
        if(n %i!=0){
            ans += max(0, n%i-k+1);
            if(k==0){
                ans--;
            }
        }
    
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,a[101010]={};
	cin>>n;
	LL sum=0;
	REP(i,n){
		cin>>a[i];
		sum+=a[i];
	}
	LL per=(n+1LL)*n/2;
	LL t=sum/per;
	if(sum%per!=0){
		cout<<"NO"<<endl;
		return 0;
	}
	a[n]=a[0];
	LL cnt=0;
	FOR(i,0,n){
		LL d=a[i+1]-a[i];
		d-=t;
		if(d>0||d%n!=0){
			cout<<"NO"<<endl;
			return 0;
		}
		cnt+=-d/n;
	}
	if(cnt!=t){
		cout<<"NO"<<endl;
		return 0;
	}
	cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 640
x,y =map(int,input().split())
ans = "No"

for i in range(x):
    val1 = 2 * i + 4 * (x - i)
    val2 = 4 * i + 2 * (x - i)
    if val1 == y:
        ans = "Yes"
        break
    if val2 == y:
        ans = "Yes"
        break
print(ans)

Measured memory_bytes: 9208
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep2(i,n) for (int i = 1; i < 40001; i+=2)
using namespace std;
using P = pair<int, int>;
using ll = long long;

int main (){
   ll x;
   cin >> x;
   vector<pair<ll, ll>> A(40001);
   A[0].first = A[0].second = 0;

   ll num = 1;
   rep2(i,40000) {
       A[i].first = num*num*num*num*num;
       A[i].second = num;
       A[i+1].first = -num*num*num*num*num;
       A[i+1].second = -num;
       num += 1;
   }
   ll a, b=1, anum = 0, bnum = 0,judge = 0;
   rep(i,40001){
       a = A[i].first;
       rep(j,40001){
           
            b = A[j].first;
           if (a == (x + b)){
               judge = 1;
               anum = A[i].second;
               bnum = A[j].second;
               break;
           }
       }
       if (judge == 1) break;
    }

    rep(i,4){
        if ((a == 0)&&(b == 0)) break; 
        else if(a == 0 )b /= bnum;
        else if( b == 0) a /= anum;
        else{
            a /= anum;
            b /= bnum;
        }
    }
    cout << a << " " << b << endl;
}

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

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

template <class T>
struct SegmentTree{
  using F = function<T(T,T)>;
  F f;
  T inf;
  int n;
  vector<T> node;

  SegmentTree(vector<T> v,T inf,F f):inf(inf),f(f){
    n = 1; while(n < v.size()) n *= 2;
    node.resize(2*n-1,inf);
    for(int i = 0; i < v.size(); i++) node[i+n-1] = v[i];
    for(int i = n-2; i >= 0; i--) node[i] = f(node[2*i+1],node[2*i+2]);
  }

  void update(int k,T val){
    k += n-1;
    node[k] = val;
    while(k > 0){
      k = (k-1) / 2;
      node[k] = f(node[2*k+1],node[2*k+2]);
    }
  }

  void add(int k,T val){
    k += n-1;
    node[k] += val;
    while(k > 0){
      k = (k-1) / 2;
      node[k] = f(node[2*k+1],node[2*k+2]);
    }
  }

  T getval(int a,int b){ return getval(a,b,0,0,n); }
  T getval(int a,int b,int k,int l,int r){
    //区間[a, b)の値を返す
    if(r <= a || b <= l) return inf;
    if(a <= l && r <= b) return node[k];
    T vl = getval(a, b, 2*k+1, l, (l+r)/2);
    T vr = getval(a, b, 2*k+2, (l+r)/2, r);
    return f(vl, vr);
  }
};

signed main(){

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

  auto f = [](int x,int y){
    return min(x,y);
  };
  SegmentTree<int> seg(a,1<<30,f);
  for(int i = 0; i < n-l+1; i++){
    if(i) cout << " ";
    cout << seg.getval(i,i+l);
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 34844
N=int(input())
A=[int(input()) for _ in range(N)]
cnt=0
buf=0
#print(A)
if N==1:
    print(A[0]//2)
else:
    for i in range(N-1):
        su=A[i]+A[i+1]
        cnt=cnt+su//2
        buf=(su//2)*2
        if buf>A[i]:
            A[i+1]=A[i+1]-(buf-A[i])
            A[i]=0
        else:
            A[i]=A[i]-buf
    #print(A,cnt)
    print(cnt)

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

#define mt make_tuple
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sqr(x) ((ll)(x) * (x))

void dfs(int s, int prosli, int preskoci, vvpii &v, vi &resenje)
{
    int nekaVrednost = 1;
    for(int i = 0; i < (int)v[s].size(); ++i)
    {
        int prvaVrednost = v[s][i].fi;
        int drugaVrednost = v[s][i].se;
        if(prvaVrednost == prosli)continue;
        if(nekaVrednost == preskoci)++nekaVrednost;

        resenje[drugaVrednost] = nekaVrednost;
        dfs(prvaVrednost, s, nekaVrednost, v, resenje);
        ++nekaVrednost;
    }
}

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

    vvpii v(n+1);

    int najveci = -1;

    vi resenje(n);

    for(int i = 0; i < n-1; ++i)
    {
        int a, b;
        cin >> a >> b;
        v[a].pb(mp(b, i));
        v[b].pb(mp(a, i));
        najveci = max(najveci, max((int)v[a].size(), (int)v[b].size()));
    }

    cout << najveci << '\n';

    dfs(1, -1, -1, v, resenje);

    for(int i = 0; i < n-1; ++i)
    {
        cout << resenje[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 8320
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
int main(void){
    ll w,h,x,y;cin>>w>>h>>x>>y;
    double res=(double)(w*h)/2;
    int jud=x*2==w&&y*2==h? 1:0;
    cout<<res<<" "<<jud<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int d = in.nextInt();
        int t = in.nextInt();
        int s = in.nextInt();
        double time = (double)d / s;
        if (time - t > 0)
            System.out.println("No");
        else
            System.out.println("Yes");
    }
}


Measured memory_bytes: 35848
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
const int inf = 1<<30, maxn = 1<<20;
using ll = long long;
const int mod = 1e9 + 7;
ll fact[maxn], inv[maxn];
void pre() {
	for(int i = 0; i < maxn; i++)
		if(i < 2) fact[i] = inv[i] = 1;
		else fact[i] = i, inv[i] = mod - (mod/i)*inv[mod%i]%mod;
	for(int i = 1; i < maxn; i++)
		fact[i] = fact[i]*fact[i-1]%mod,
		inv[i] = inv[i]*inv[i-1]%mod;
}
ll nck(ll n, ll k) {
	if(k < 0 || k > n) return 0;
	ll t = fact[n]*inv[k]%mod;
	return t*inv[n-k]%mod;
}
ll A(ll n, ll k) {
	if(k < 0 || k > n) return 0;
	return fact[n]*inv[n-k]%mod;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	pre();
	ll n, m;
	cin >> n >> m;
	ll ans = 0;
	for(int i = 0; i <= n; i++) {
		ll t = A(m-i, n-i)*A(m-i, n-i)%mod;
		t = t * nck(n, i) % mod;
		t = t * A(m, i) %mod;
		if(i&1) ans = (mod + ans - t)%mod;
		else ans = (ans + t)%mod;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 20004
<?php
    // データ読み込み部
    fscanf(STDIN, "%d", $N);
    $A = explode(" ", trim(fgets(STDIN)));

    // 石の数の総計
    $total = array_sum($A);
    // 1回の操作で取り出す石の数
    $one = (1 + $N) * $N / 2;
    // 取り出す回数を算出
    $round = $total / $one;
    // 切れ目の数カウント用
    $cut = 0;
    // 取り出す回数が整数でない場合はNOを出力して終了
    if (floor($round) != $round) {
        echo "NO\n";
        exit;
    }

    // 配列の最後に1番目の箱をつける
    $A[] = $A[0];
    for ($i = 0; $i < $N; $i++) {
        // 「右の箱の石の数」引く「左の箱の石の数」引く「取り出す回数」
        $diff = $A[$i+1] - $A[$i] - $round;
        if ($diff < 0) {
            // ここがマイナスになる場合には切れ目があるので切れ目の回数を計算
            $kaisuu = floor($diff / $N);
            // 切れ目の数がマイナスで増えていく
            $cut += $kaisuu;
        }
    }

    // 「切れ目の数」と「取り出す回数」が同じならYES
    if ($round == -$cut) {
        echo "YES\n";
    } else {
        echo "NO\n";
    }


Measured memory_bytes: 10868
n,m=map(int,input().split())
if abs(n-m)>=2:
    print(0)
else:
    ans=1
    for i in range(1,n+1):
        ans=ans*i%(10**9+7)
    for i in range(1,m+1):
        ans=ans*i%(10**9+7)
    print(ans%(10**9+7) if n!=m else 2*ans%(10**9+7))

Measured memory_bytes: 3060
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])

Measured memory_bytes: 94284
#include <bits/stdc++.h>
#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() {
    ll n, k;
    cin >> n >> k;
    
    if(n % k == 0){
        cout << 0 << endl;
        return 0;
    }
    
    cout << min(n % k, abs(n % k - k)) << endl; 
    
    return 0;
}

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

int main(){
    int n,k,i;
    scanf("%d %d",&n,&k);
    unsigned long long *a=(unsigned long long *)malloc(n*sizeof(unsigned long long));
    for(i=0;i<n;i++){
        scanf("%llu", a+i);
    }
    for(i=0;i<n-k;i++){
        if(a[i]<a[i+k]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
typedef long long ll;
typedef long double ld;
using namespace std;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;


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

  int a, b;
  cin >> a >> b;
  cout << max(0, a - 2 * b) << endl;

  return 0;
}

Measured memory_bytes: 256
using System.Collections.Generic;
using System.Linq;
public class PictureMatching
    {
        private static int[] Item;

        public static void Main(string[] args)
        {
            Input();
            Method();
            System.Console.ReadLine();
        }

        private static void Input()
        {
            System.Console.ReadLine();
            Item = ToIntArray(System.Console.ReadLine().Split(' '));
        }

        private static void Method()
        {
            int cnt = 0;
            for (int i = 0; i < Item.Length - 1; i++)
            {
                for (int j = Item.Length - 1; j > i; j--)
                {
                    if (Item[j] < Item[j - 1])
                    {
                        var temp = Item[j];
                        Item[j] = Item[j - 1];
                        Item[j - 1] = temp;
                        cnt++;
                    }
                }
            }

ConsoleWrite();
            System.Console.WriteLine(cnt);
        }
        private static void ConsoleWrite()
        {
            for (int i = 0; i < Item.Length; i++)
            {
                System.Console.Write(Item[i]);
                if (i != Item.Length - 1)
                {
                    System.Console.Write(" ");
                }
            }
            System.Console.WriteLine("");
        }

        private static int[] ToIntArray(string[] str)
        {
            IEnumerable<int> intArray = str.Select(x => int.Parse(x));
            return intArray.ToArray();
        }
    }

Measured memory_bytes: 9604
#include <iostream>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	char a[4], b[4];
	cin >> a >> b;

	cout << ((a[0] == b[2] && a[1] == b[1] && a[2] == b[0]) ? "YES" : "NO") << endl;

	return 0;
}

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

int x[100005],d[100005];

int main(void){
    int n,m,ans=0;cin>>n>>m;
    for(int i=0;i<m;i++)cin>>x[i];
    sort(x,x+m);
    for(int i=1;i<m;i++)d[i-1]=x[i]-x[i-1];
    sort(d,d+m-1);
    for(int i=0;i<m-n;i++)ans+=d[i];
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 1024
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        vs: [usize; n],
        cs: [usize; n]
    }

    let result = vs.into_iter().zip(cs.into_iter()).filter_map(|(v, c)| {
        if v < c {
            None
        } else {
            Some(v - c)
        }
    }).fold(0, |sum, a| sum + a);
    println!("{}", result);
}


Measured memory_bytes: 4352
# from sys import exit
N,K = [int(n) for n in input().split()]
# N = int(input())
# a = [int(input()) for _ in range(N)]
S = list(str(input()))
L = len(S)
# T = str(input())
# exit()
S[K-1] = S[K-1].lower()
print("".join(S))


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
struct edge {
  ll to, cost;
};

int main() {
  string S, T; cin >> S >> T;
  int ans = pow(10, 9) + 7;
  for(int i = 0; i < S.size() - T.size() + 1; ++i) {
    int res = 0;
    for(int k = 0; k < T.size(); ++k) {
      if(S[i + k] != T[k]) res++;
    }
    if(ans > res) ans = res;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int A, B, C, memo[105][105][105];

int func(int a, int b, int c)
{
    if(a > 100 || b > 100 || c > 100)
    {
        return 1005;
    }
    if(a == b && a == c)
    {
        return 0;
    }
    int &ret = memo[a][b][c];
    if(ret != -1)
    {
        return ret;
    }
    ret = 987654321;
    ret = min(ret, func(a + 1, b + 1, c) + 1);
    ret = min(ret, func(a + 1, b, c + 1) + 1);
    ret = min(ret, func(a, b + 1, c + 1) + 1);
    ret = min(ret, func(a + 2, b, c) + 1);
    ret = min(ret, func(a, b + 2, c) + 1);
    ret = min(ret, func(a, b, c + 2) + 1);
    return ret;
}

int main()
{
    scanf("%d %d %d", &A, &B, &C);
    memset(memo, -1, sizeof memo);
    printf("%d", func(A, B, C));
}

Measured memory_bytes: 4736
n,m=map(int,input().split())
p=[int(i) for i in input().split()]
l=[0 for i in range(n)]
for i in range(n):
    l[p[i]-1]=i
xy=[]

par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(m):
    a=[int(j)-1 for j in input().split()]
    xy.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

ans=0
for i in range(n):
    if root(i)==root(l[i]):
        ans+=1
    
print(ans)   

Measured memory_bytes: 30196
N, A, B = map(int, input().split())
lst = []
for _ in range(N):
    lst += [int(input())]

def check(T):
    t = 0
    for i in range(N):
        if lst[i] > B * T:
            t += max((lst[i]-B*T + (A-B-1))//(A-B), 0)
        else:
            pass
    return t <= T

la = -1
ua = 10 ** 9
ans = 10 ** 9
while ua - la > 1:
    mid = (la + ua)//2
    if check(mid):
        ans = min(ans, mid)
        ua = mid
    else:
        la = mid
print (ans)

Measured memory_bytes: 7076
#include<iostream>
using namespace std;
int main(){
    int S, h, m, s;
    cin >> S;
    h = S / 3600;
    m = (S % 3600) / 60;
    s = (S % 3600) % 60;
    cout << h << ":" << m << ":" << s << endl;
    return 0;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

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

const int INF=1001001001;

signed main(){
	int N;cin>>N;
	vint A(N);rep(i,N)cin>>A[i];

	vint pre(N+1),suf(N+1);
	pre[0]=-INF;
	rep(i,N)pre[i+1]=max(pre[i],A[i]);
	suf[N]=-INF;
	for(int i=N-1;i>=0;i--)suf[i]=max(suf[i+1],A[i]);

	rep(i,N){
		printf("%lld\n",max(pre[i],suf[i+1]));
	}
	return 0;
}

Measured memory_bytes: 6272
n = int(input())
XY = []
for _ in range(n):
    a = int(input())
    XY.append([list(map(int, input().split())) for __ in range(a)])
ans = 0
for i in range(1, 2 ** n):
    S = []
    F = []
    for j in range(n):
        if i >> j & 1:
            S.append(j + 1)
        else:
            F.append(j + 1)
    consistent = True
    for s in S:
        xy = XY[s - 1]
        for x, y in xy:
            if y == 1 and x in F: consistent = False
            if y == 0 and x in S: consistent = False
    if consistent:
        ans = max(ans, len(S))
print(ans)

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

int main() {
  long long A,B,N;
  cin >> A >> B >> N;
  long long x;
  x = min(B-1, N);
  cout << floor(A*x/B) - floor(x/B) * A << endl;
  return 0;
}




Measured memory_bytes: 3792
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
using lint=long long;
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int h,n;cin>>h>>n;
  vector<int> a(n);
  vector<int> b(n);
  rep(i,n)cin>>a[i]>>b[i];
  vector<int> dp(h+5,inf);
  dp[0]=0;
  rep(i,n){
      rep(j,h){
          int buf=min(h,j+a[i]);
          dp[buf]=min(dp[buf],dp[j]+b[i]);
      }
  }
  cout<<dp[h]<<"\n";
  return 0;
}

Measured memory_bytes: 3656
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define let const auto
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'

int main()
{
   cin.tie(0), ios::sync_with_stdio(false);
   int a, b, c, d;
   cin >> a >> b >> c >> d;

   outl( min(a,b) + min(c,d) );
}



Measured memory_bytes: 256
import numpy

S = numpy.array([ord(s) for s in input()])
T = numpy.array([ord(s) for s in input()])

TL = len(T)
SL = len(S)

C = [numpy.count_nonzero(S[i:i + TL] != T) for i in range(SL - TL + 1)]
print(numpy.min(C))

Measured memory_bytes: 27260
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
int N;
ll A[200001];
ll sum[200005];
int nibun(int st,int ed,ll H,ll hiku){
int ret=-1;
while ( st <= ed ){
int h = (st+ed)/2;
ll y = sum[h] - hiku;
if( y > H ){
ed=h-1;
ret = h;
} else if( y < H ){
st=h+1;
} else {
ret = h;
break;
}
}
return ret;
}
 
ll check(int id){
ll ret=-1;
ll st = 0,ed = sum[N];
// ll st = 213,ed = 213;
while( st <= ed ){
ll h = (st+ed)/2;
bool f=false;
int r = nibun(id,id+N-3,h,sum[id-1]);
if( r > -1 ){
r = nibun(r+1,id+N-2,h,sum[r]);
if( r > -1 ){
if( sum[id+N-1] - sum[r] >= h ){
f=true;
}
}
}
if( f ){
// printf("ok %lld\n",h);
st=h+1;
ret = h;
} else {
// printf("ng %lld\n",h);
ed=h-1;
}
}
return ret;
}
 
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%lld",&A[i]);
}
for(int i=1;i<=N;i++){
A[i+N] = A[i];
}
for(int i=1;i<=2*N;i++){
sum[i]=sum[i-1]+A[i];
// printf("%lld\n",sum[i]);
}
 
ll res = 0;
for(int i=1;i<=N;i++){
ll ret = check(i);
// printf("%lld\n",ret);
res = max(res,ret);
}
printf("%lld\n",res);
}

Measured memory_bytes: 4312
def main():
    MOD = 998244353
    N = int(input())
    D = [int(i) for i in input().split()]
    if D[0] != 0:
        return print(0)
    from collections import Counter
    c = Counter(D)
    ans = 1
    for d in D[1:]:
        if d == 0:
            return print(0)
        ans *= c[d-1]
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 62700
def main():
    a, b = input().split()

    pattern = {
        ("H", "H"): "H",
        ("H", "D"): "D",
        ("D", "H"): "D",
        ("D", "D"): "H",
    }
    ans = pattern[(a, b)]
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e9)+1;
const ll mod = ll(1e9)+7;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll t = 1;
    rep1(i, n){
        t *= i;
        t %= mod;
    }
    return t;
}

ll power(ll a, ll b){
    a %= mod;
    if(b == 0){
        return 1;
    }
    ll ans = power(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}

ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    ll ans = 1;
    for(ll i = 0; i < b; i++) {
        ans *= (a - i);
        ans %= mod;
        ans *= power(i + 1, mod - 2);
        ans %= mod;
    }
    return ans;
}

struct UnionFind {
    vector<ll> par;
    vector<ll> rank;
    vector<ll> Size;
    UnionFind(ll n = 1) {
        init(n);
    }
 
    void init(ll n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        rep0(i, n + 1){
            par[i] = i;
            rank[i] = 0;
            Size[i] = 1;
        }
    }
 
    ll root(ll x) {
        if (par[x] == x) {
            return x;
        }
        else {
            ll r = root(par[x]);
            return par[x] = r;
        }
    }
 
    bool same(ll x, ll y) {
        return root(x) == root(y);
    }
 
    bool merge(ll x, ll y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        return true;
    }
 
    ll size(ll x){
        return Size[root(x)];
    }
};

int main(){
    ll n,m,k;
    cin >> n >> m >> k;
    UnionFind f(n);
    vector<vector<ll>> Friend(n,vector<ll>());
    vector<ll> ans(n,0);
    vector<pair<ll, ll>> Block;
    rep0(i, m){
        ll a,b;
        cin >> a >> b;
        --a;
        --b;
        f.merge(a, b);
        Friend.at(a).push_back(b);
        Friend.at(b).push_back(a);
        --ans[a];
        --ans[b];
    }
    rep0(i, k){
        ll a,b;
        cin >> a >> b;
        --a;
        --b;
        Block.push_back(make_pair(a, b));
    }
    
    vector<bool> check(n,false);
    rep0(i, n)ans[i] += f.size(i) - 1;
    
    rep0(i, k){
        if(f.same(Block[i].first, Block[i].second)){
            --ans[Block[i].first];
            --ans[Block[i].second];
        }
    }
    rep0(i, n)ans[i] = max(ans[i],0ll);
    rep0(i, n)pf(ans[i]);
    return 0;
}


Measured memory_bytes: 11884