akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define ROF(i,b,a) for (int i=(b);i>=(a);--i)
typedef long long LL;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}

const int MAXN=200005;
char s[MAXN];
int n,m,l,a[MAXN][26],b[26],c[26],f[MAXN];
void dfs(int x) {
	if (f[x]==0) {
		memset(b,0,sizeof(b));
		FOR(y,x+1,n) b[s[y]-'a']=1;
		FOR(y,0,25) if (!b[y]) { printf("%c",char('a'+y)); return; }
	}
	int y=-1,z;
	FOR(j,0,25)
	if (y==-1||z>f[a[x][j]]) y=j,z=f[a[x][j]];
	printf("%c",char('a'+y));
	dfs(a[x][y]);
}
int main(){
	scanf("%s",s+1); n=strlen(s+1);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b)); m=l=0;
	FOR(j,0,25) c[j]=n+1;
	ROF(i,n,1) {
		int x=s[i]-'a';
		FOR(j,0,25) a[i][j]=c[j];
		c[x]=i;
		f[i]=l;
		if (!b[x]) {
			b[x]=1; m++;
			if (m==26) {
				l++; m=0; memset(b,0,sizeof(b));
			}
		}
	}
	FOR(j,0,25) a[0][j]=c[j];
	f[0]=l; dfs(0);
	return 0;
}

/*
*/


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

using namespace std;

typedef long long ll;

int main()
{
    int N;
    while (cin >> N, N) {
        ll res = -114514;
        bool ok = 0;
        vector<ll> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
            res = max(res, a[i]);
        }

        if (res > 0) ok = 1;
        
        ll sum = 0;
        for (int i = 0; i < N; i++) {
            sum += a[i];
            if (sum < 0) sum = 0;
            if (ok) {
                res = max(res, sum);
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3064
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val N = nextInt()
    val AB = Array(N) {
        val (a, b) = nextIntList()
        P(a, b)
    }.sortedBy { it.B }
    var t = 0L
    for ((a, b) in AB) {
        t += a
        if (t > b) {
            println("No")
            return
        }
    }
    println("Yes")
}

data class P(val A: Int, val B: Int)

Measured memory_bytes: 69536
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [[INF] * (H+1) for i in range(N+1)]

    for i in range(1,N+1):
        for j in range(1, H+1):
            if j-A[i-1] > 0:
                dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])
            else:
                dp[i][j] = min(dp[i-1][j], B[i-1])

    # for i in dp:
    #     print(i)
    print(dp[N][H])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 118896
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>

using namespace std;
int main() {
    int n,k;
    string s;
    cin>>n>>k>>s;
    lp(i,n){
        if(i!=k-1)
            cout<<s[i];
        else
            cout<<char(s[i]+32);
    }
    cout<<endl;
}


Measured memory_bytes: 256
import math

n = int(input())
x = [int(e) for e in input().split()]
y = [int(e) for e in input().split()]
D1=0
D2=0
D3=0
Di=abs(x[0]-y[0])
for i in range(n):
    D1 = D1 + (abs(x[i]-y[i]))
    D2 = D2 + (abs(x[i]-y[i]))**2
    D3 = D3 + (abs(x[i]-y[i]))**3
    if abs(x[i]-y[i]) > Di:
        Di = abs(x[i]-y[i])
print(D1)
print(math.sqrt(D2))
print(D3**(1/3))
print(Di)


Measured memory_bytes: 5700
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int H, W;
  cin>>H>>W;
  vector<string> S(H);
  for(int i=0;i<H;++i) cin>>S[i];
  priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int> >, greater<tuple<int, int, int, int> > > que; // cost, black, zahyo
  if(S[0][0]=='.') que.push(mt(0, 0, 0, 0));
  else que.push(mt(1, 1, 0, 0));
  tuple<int, int, int, int> state;
  int cost, black, x, y;
  int ans[H][W];
  for(int i=0;i<H;++i) {
    for(int j=0;j<W;++j) {
      ans[i][j] = inf;
    }
  }
  while(!que.empty()) {
    state = que.top();que.pop();
    cost = get<0>(state);
    black = get<1>(state);
    x = get<2>(state);
    y = get<3>(state);
    if(ans[x][y]<=cost) continue;
    ans[x][y] = cost;
    if(black) {
      if(x<H-1) {
        if(S[x+1][y]=='#') {
          que.push(mt(cost, black, x+1, y));
        }
        else {
          que.push(mt(cost, black-1, x+1, y));
        }
      }
      if(y<W-1) {
        if(S[x][y+1]=='#') {
          que.push(mt(cost, black, x, y+1));
        }
        else {
          que.push(mt(cost, black-1, x, y+1));
        }
      }
    }
    else {
      if(x<H-1) {
        if(S[x+1][y]=='#') {
          que.push(mt(cost+1, black+1, x+1, y));
        }
        else {
          que.push(mt(cost, black, x+1, y));
        }
      }
      if(y<W-1) {
        if(S[x][y+1]=='#') {
          que.push(mt(cost+1, black+1, x, y+1));
        }
        else {
          que.push(mt(cost, black, x, y+1));
        }
      }
    }
  }
  /**
  for(int i=0;i<H;++i) {
    for(int j=0;j<W;++j) {
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }
  **/
  cout<<ans[H-1][W-1]<<endl;
}



Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;
 
typedef long long i64;
typedef pair<int, int> pi;
 
template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;
 
i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

  int n, k;
  cin >> n >> k;
  vt<int> p(n);
  rep(i, 0, n) cin >> p[i];

  vt<double> v(n);
  rep(i, 0, n) {
    int sum = p[i] * (p[i] + 1) / 2;
    v[i] = sum * (1 / (double)p[i]);
  }

  double ans = 0, num = 0;
  rep(i, 0, k - 1) {
    num += v[i];
  }
  rep(i, k - 1, n) {
    num += v[i];
    ans = max(ans, num);
    num -= v[i + 1 - k];
  }
  cout << fixed << setprecision(10) << ans << endl; 
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int K = sc.nextInt();
	int count = 0;
	for(int a=1;a<=K;a++){
	    for(int b=1;b<=K;b++){
		for(int c=1;c<=K;c++){
		    count += gcd(gcd(a,b),c);
		}
	    }
	}
	System.out.print(count);
    }
    public static int gcd(int p,int q){
	if(p%q==0) return q;
	return gcd(q,p%q);
    }
}


Measured memory_bytes: 35624
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
        cin >> N;
            if(N % 2 == 0){
                cout << 0.5 << endl;
            }else{
                cout << ((N + 1.0) * 0.5) / N << endl;
            }
    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
have = [0] * N
for i in range(K):
    d = int(input())
    As = list(map(int,input().split()))
    for j in range(d):
        have[As[j]-1] += 1

ans = 0
for i in range(N):
    if have[i] == 0:
        ans += 1
print(ans)


Measured memory_bytes: 67616
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll MOD = 1e9+7;

int n;
string s;
map<char, int> mp;

int main() {
    cin >> n >> s;
    for(auto c : s)
        mp[c]++;

    ll ans = 1;
    for(auto p : mp) {
        ans *= p.second + 1;
        ans %= MOD;
    }
    cout << ans - 1 << endl;
}


Measured memory_bytes: 512
N = int(input())
n = str(N)
x = int(n[-1])
if x == 2 or x == 4 or x == 5 or x == 7 or x == 9:
    print('hon')
elif x == 0 or x == 1 or x == 6 or x == 8:
    print('pon')
else:
    print('bon')

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()


int main(){
    ll a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main(){
    int n, a, b, ans = 0;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++){
        int num = 0;
        num += (i / 10000) + (i / 1000 % 10) + (i / 100 % 10) + (i / 10 % 10) + (i % 10);
        if(a <= num && num <= b){
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<int>cnt(m);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int a;
      cin>>a;
      a--;
      cnt[a]++;
    }
  }
  int gu=0;
  for(int i=0;i<m;i++){
    if(cnt[i]==n){
      gu++;
    }
  }
  cout<<gu<<endl;
}
    
  


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

typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pp;
typedef pair<ll,pair<ll,ll> > ppp;

#define mk make_pair
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define parr(A,n) for(int xxx=0;xxx<n;xxx++){cout<<A[xxx]<<" ";}cout << "\n";
#define MOD 1000000007
#define endl "\n"
inline ll power(ll x, ll y)
{
    ll res = 1;x = x % MOD;
    while (y > 0){if (y & 1) res = (res*x) % MOD;y = y>>1;x = (x*x) % MOD;}
    return res%MOD;
}
inline ll sum(ll a, ll b){b = ((b%MOD) + MOD)%MOD;a = ((a%MOD) + MOD)%MOD;return ((a+b)%MOD + MOD)%MOD;}
inline ll mul(ll a, ll b){return ((a*b)%MOD + MOD)%MOD;}

int main() {
	boost;
	ll n,x;
	cin >> n >> x;
	ll A[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> A[i];
	}
	sort(A,A+n);
	ll left = x;
	ll ans = 0;
	for (int i = 0; i < n; ++i)
	{
		if(left >=A[i]){
			left-=A[i];
			ans++;
		}
	}
	if(left > 0 && ans==n){
		ans--;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (N, R) = listOfInt()
    val ans = if (N < 10) R + 100 * (10 - N) else R
    println(ans)
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)


Measured memory_bytes: 37904
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for(int n=0;n<N;n++) a[n]=sc.nextInt();
        
        int absMax=0;
        for(int n=0;n<N;n++){
        	if(Math.abs(a[absMax]) <= Math.abs(a[n])){
        		absMax = n;
        	}
        }
        
        if(a[absMax]==0){
        	System.out.println("0");
        }else if(a[absMax]>0){
        	System.out.println(2*N-2);
        	for(int n=0;n<N;n++){
        		if(n!=absMax)System.out.println((absMax+1)+" "+(n+1));
        	}
        	for(int n=1;n<=N-1;n++){
        		System.out.println(n+" "+(n+1));
        	}
        }else{
        	System.out.println(2*N-2);
        	for(int n=0;n<N;n++){
        		if(n!=absMax)System.out.println((absMax+1)+" "+(n+1));
        	}
        	for(int n=N;n>=2;n--){
        		System.out.println(n+" "+(n-1));
        	}
        }
    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;

LL dp[1001][1001];
int a[1001][1001];
LL f[1001][1001];
map<P,int> ma;

int dfs(int i,int j){
    if(j==-1) return 0;
    if(f[i][j]&&dp[i][j]==-1){
        return INF;
    }
    if(~dp[i][j]) return dp[i][j];
    int ret = 0;
    f[i][j] = true;
    ret = max(ret,dfs(i,j-1)+1);
    ret = max(ret,dfs(a[i][j],ma[mp(a[i][j],i)]-1)+1);
    return dp[i][j] = ret;
}

int main(){
    LL n;cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            cin >> a[i][j];
            a[i][j]--;
            ma[mp(i,a[i][j])]= j;
        }
    }
    memset(dp,-1,sizeof(dp));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans,dfs(i,j));
        }
    }
    if(ans >= INF){
        puts("-1");
    }
    else{
        cout << ans - 1 << endl;
    }
    return 0;
}



Measured memory_bytes: 82432
#include <iostream>
#include <algorithm>

using namespace std;

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

	int result = 0;
	if (a + b >= 2 * c) {
		if (x >= y)
			result += 2 * c * y + a * (x - y);
		else
			result += 2 * c * x + b * (y - x);
	}
	else
		result += a * x + b * y;

	if (result > 2 * c * max(x, y))
		result = 2 * c * max(x, y);

	cout << result << endl;
}

Measured memory_bytes: 256
//  Lower

#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>

using namespace std;
typedef long long LL;
int main()
{
    int N;
    vector<LL> H;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        H.push_back(tmp);
    }
    int m = 0;
    int tmp = 0;
    for (int i = 0; i < N; i++) {
        
        if (i == 0) {
            continue;
        }
        
        if (H[i-1] >= H[i]) {
            tmp++;
            m = max(m,tmp);
        }
        else {
            tmp = 0;
        }
    }
    cout << m << endl;
}



Measured memory_bytes: 1400
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {
	int x,y,z;
	cin>>x>>y>>z;
	x-=z;y+=z;
	cout<<x/y;
		
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3608
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [-1] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        global odd_cycle
        odd_cycle = True
        return

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


odd_cycle = False
dfs(1, dic[1], 0)
if odd_cycle:
    ans = 0.5 * n * (n-1) - m
else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print(int(ans))


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

#define MAXK 100000
#define INF (1<<30)
int d[MAXK];

int main() {
  int K; scanf("%d", &K);
  for(int i = 0; i < K; ++i) d[i] = INF;
  deque<int> deq = {1}; d[1] = 1;
  while(!deq.empty()) {
    int v = deq.front(); deq.pop_front();
    if(v == 0) break;
    int w = (v + 1) % K, u = (v * 10) % K;
    if(d[v] + 1 < d[w]) {
      d[w] = d[v] + 1; deq.push_back(w);
    }
    if(d[v] < d[u]) {
      d[u] = d[v]; deq.push_front(u);
    }
  }
  printf("%d\n", d[0]);
  return 0;
}


Measured memory_bytes: 896
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int n,m,x,y,a[105],b[105];
	scanf("%d %d %d %d",&n,&m,&x,&y);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	if(a[n]<b[1]&&x<b[1]&&y>a[n])
		printf("No War");
	else
		printf("War");
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
vp in;
pii p1,p2;
bool fil[5010][5010];
bool f(pii w){
	int a=w.first,b=w.second;
	if(a<0||b<0||a>=5010||b>=5010)return false;
	return true;
}
int main(){
	int n;
	while(cin>>n,n){
		rep(i,5010)rep(j,5010)fil[i][j]=0;
		in=vp(n);
		rep(i,n){
			int a,b;
			cin>>a>>b;
			fil[a][b]=1;
			in[i]=pii(a,b);
		}
		int out=0;
		rep(i,n){
//			if(i%100==0)cout<<i<<endl;
			rep(j,n)if(i!=j){
				int a=in[i].first-in[j].first,b=in[i].second-in[j].second;
				p1=pii(in[i].first-b,in[i].second+a);
				p2=pii(in[j].first-b,in[j].second+a);
				if(f(p1)==0||f(p2)==0)continue;
				if(fil[p1.first][p1.second]&&fil[p2.first][p2.second])out=max(out,a*a+b*b);
			}
		}
		cout<<out<<endl;
	}
}

Measured memory_bytes: 25768
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>
using namespace std;

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 100005
#define LOG_MAX 20
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define in(x) scanf("%d", &x)
#define inl(x) scanf("%lld", &x)
#define in2(x, y) scanf("%d %d", &x, &y)
#define inl2(x, y) scanf("%lld %lld", &x, &y)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define finish(x) {cout<<x<<'\n'; return;}
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const char en = '\n';

/* Modulo exponentiation */
LL power(LL base, LL exp, LL ans) {
	if(!exp) return ans % MOD;
	if(exp&1) ans = (ans * base) % MOD;
	return power((base * base) % MOD, exp>>1, ans);
}

void solve() {
	LL n;
	inl(n);
	if(n <= 1) finish(0);
	LL ans = (power(10, n, 1) + power(8, n, 1)) % MOD;
	ans = (ans - (2 * power(9, n, 1)) % MOD + MOD) % MOD;
	cout<<ans<<en;
}

int main() {
	int t = 1;
	
	//~cin>>t;
	while(t--) {
		solve();
	}
    return 0;
}


Measured memory_bytes: 3740
#include <stdio.h>

int search(int key, int S[], int n);

int main(){
  int n,q,key,i,count=0,S[100000];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(search(key, S, n)){
      count++;
    }
  }
  printf("%d\n",count);
  
  return 0;
}

int search(int key, int S[], int n){
  int left,right,mid;
  left = 0;
  right = n;
  while(left<right){
    mid = (left+right)/2;
    if(S[mid]==key){
      return 1;
    }else if(key<S[mid]){
      right = mid;
    }else{
      left = mid+1;
    }
  }
  return 0;
}



Measured memory_bytes: 2128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int f(int x){
    map<int,int> d;
    int t = x;
    for(int i=2; i*i<=x; ++i){
        while(t%i==0){
            ++d[i];
            t/=i;
        }
    }
    if(t>1) ++d[t];

    int ret = 1;
    for(const auto &p:d) ret *= p.se+1;
    return ret;
}

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

    int a = 1;
    while(f(a)!=n) ++a;
    cout << a << endl;
    return 0;
}



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

int n;

void solve() {
    string s = to_string(n);
    if (s.at(0) == '7' || s.at(1) == '7' || s.at(2) == '7') {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

Measured memory_bytes: 3696
#include<stdio.h>
#include<string.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n,alp[30],alpmin[30];
	char s[51],num;

	memset(alpmin,0,sizeof(alpmin));

	scanf("%d",&n);
	FOR(i,0,n){
		scanf("%s",s);
		memset(alp,0,sizeof(alp));
		FOR(j,0,strlen(s)){
			num = s[j] - 'a';
			alp[num]++;
		}
		if(i == 0){
			FOR(j,0,30){
				alpmin[j] = alp[j];
			}
		}else{
			FOR(j,0,30){
				if(alpmin[j] > alp[j]) alpmin[j] = alp[j];
			}
		}

	}

	FOR(i,0,30){
		while(alpmin[i]--){
			printf("%c",i+'a');
		}
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <iomanip>
using namespace std;
#define Would
#define you
const int INF = 999999999;
const int MOD = 1e9 + 7;
const double pi = 3.141592653589793238;

long long n, k[1005];
set<long long>s;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int l[5];
		for (int i = 0; i < 3; ++i) { cin >> l[i]; }
		sort(l, l + 3);
		s.insert(l[0] + 10000 * l[1] + 100000000 * l[2]);
	}
	cout << n - s.size() << endl;
}


Measured memory_bytes: 3200
#include<iostream>
using namespace std;
static const int MAX = 3000;

int main(){
    int buff[MAX][2];
    
    for(int i=0; i<MAX; i++){
        cin >> buff[i][0] >> buff[i][1];
        if(buff[i][0] == 0 && buff[i][1] == 0){
            buff[i][0] = -1;
            break;
        }
    }
    
    for(int i=0; i<MAX; i++){
        if(buff[i][0] == -1)break;
        if(buff[i][0] < buff[i][1])
            cout << buff[i][0] << " " << buff[i][1] << endl;
        else
            cout << buff[i][1] << " " << buff[i][0] << endl;
    }
    return 0;
}


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


char rmsg[50];
int len;
void J();
void C();
void E();
void A();
void P();
void M();


int main(){
  int n;
  char msger[10];

  cin >> n;
  for (int i=0;i<n;i++){
    cin >> msger >> rmsg;
    // cin >> rmsg;
    len=strlen(rmsg);
    //cout << rmsg << endl;
    for (int j=strlen(msger)-1;j>=0;j--){
      switch (msger[j]){
      case 'J':J();break;
      case 'C':C();break;
      case 'E':E();break;
      case 'A':A();break;
      case 'P':P();break;
      case 'M':M();break;
      }
      //cout <<msger[j]<<" "<< rmsg << endl;
    }
    cout << rmsg << endl;
  }
}

void C(){
  char t=rmsg[0];

  for (int i=0;i<len-1;i++){
    rmsg[i]=rmsg[i+1];
  }
  rmsg[len-1]=t;
}
void J(){
  char t=rmsg[len-1];

  for (int i=len-1;i>0;i--){
    rmsg[i]=rmsg[i-1];
  }
  rmsg[0]=t;
}
void E(){
  char t;
  if (len<=1)return;
  for (int i=0;i<(len/2);i++){
    t=rmsg[i];
    rmsg[i]=rmsg[i+((len+1)/2)];
    rmsg[i+((len+1)/2)]=t;
  }
}
void A(){
  char t;
  for (int i=0;i<len-i;i++){
    t=rmsg[i];
    rmsg[i]=rmsg[len-i-1];
    rmsg[len-i-1]=t;
  }
}
void P(){
  for (int i=0;i<len;i++){
    if ('0'<rmsg[i]&&rmsg[i]<='9'){
      rmsg[i]--;
    }else if (rmsg[i]=='0'){
      rmsg[i]='9';
    }
  }
}
void M(){
  for (int i=0;i<len;i++){
    if ('0'<=rmsg[i]&&rmsg[i]<'9'){
      rmsg[i]++;
    }else if (rmsg[i]=='9'){
      rmsg[i]='0';
    }
  }
}

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

int main(){
  int N,Q,count=0;
  string S;
  cin>>N>>Q>>S;
  vector<vector<int>> lr(Q,vector<int>(2));
  vector<int> vec(N,0);
  
  for(int i=0;i<Q;i++){
    for(int j=0;j<2;j++){
      cin>>lr.at(i).at(j);
    }
  }
  for(int i=0;i<N-1;i++){
    if(S.at(i)=='A'&&S.at(i+1)=='C')
      vec.at(i+1)=vec.at(i)+1;
    else
      vec.at(i+1)=vec.at(i);
  }

  for(int i=0;i<Q;i++){
    cout<<vec.at(lr.at(i).at(1)-1)-vec.at(lr.at(i).at(0)-1)<<endl;
  }
}


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

using namespace std;
using ll = long long;
using P = pair<ll,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 ALL(x) (x).begin(),(x).end()
#define FILL(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){

  int n;
  cin >> n;
  int k = (n+1)/2;
  cout << fixed << setprecision(15);
  cout << (double)k/n;


  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

	int res10 = -1;
	int res5 = -1;
	int res1 = -1;

	for(a=0;a<=n;a++){
		for(b=0;b<=n;b++){
			if(y == 10000*a + 5000*b + 1000*(n-a-b) && n-a-b >= 0){
				res10 = a;
				res5 = b;
				res1 = n-a-b;
			}
		}
	}

	cout << res10 << " " << res5 << " " << res1 << endl;


	return 0;
}

Measured memory_bytes: 256
import math
lst = [int(input()) for _ in range(5)] 

lst1 = []
min1 = 9
num1 = 0

for i, l in enumerate(lst):
    lst1.append(math.ceil(l/10)*10)
    if min1 > l%10 and l%10!=0:
        min1 = l%10
        num1 = i
lst1[num1] = lst[num1]

print(sum(lst1))

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin>>s>>t;
    int m=s.length(), n=t.length();
    int LCS[m+1][n+1];
    for(int i=0; i<m+1; i++)
    {
    	for(int j=0; j<n+1; j++)
    	{
    		if(i==0||j==0) LCS[i][j]=0;
    		else if(s[i-1]==t[j-1])
    		{
    			LCS[i][j]=LCS[i-1][j-1]+1;
    		}
    		else
    		{
    			LCS[i][j]=max(LCS[i-1][j], LCS[i][j-1]);
    		}	
    	}
    }
    int lcs=LCS[s.length()][t.length()];
    string ans="";
    while(lcs--)
    {
    	if(s[m-1]==t[n-1]) 
    	{
    		ans+=s[m-1];
    		m--, n--;
    	}
    	else if(LCS[m-1][n]>LCS[m][n-1]) 
    	{
    		m--;
    		lcs++;
    	}
    	else
   		{
   			n--;
   			lcs++;
   		}
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;

    return 0;
}
 

Measured memory_bytes: 35456
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		int a = 0;
		int b = 0;
		for(var i=0;i<str.Length;i++){
			if(str.Substring(i,1)=="0"){
				a++;
			} else {
				b++;
			}
		}
		Console.WriteLine(Math.Min(a,b)*2);
	}
}

Measured memory_bytes: 13280
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
const long double Pi=acos(-1);
int main(){
  ll A,B,C,D,K;
  cin>>A>>B>>C>>D>>K;
  cout<<(C-A)*60+(D-B)-K<<endl;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int a, b, t;

int main()
{
    int i, j;
    scanf("%d%d%d", &a, &b, &t);
    printf("%d", t/a*b);
}


Measured memory_bytes: 256
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back

#define eb emplace_back
#define mod   1000000007
#define PI 2*acos(0.0)
#define all(r)(r).begin(),(r).end()
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define inf 1000000000000000000
#define N 200000
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};


//=============================================ASIFAZAD==============================================//

int32_t main()
{
    io;
    int n, x, t;
    cin>>n>>x>>t;
    int ans = ceil(n/double(x))*t;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3644
import java.util.Scanner;
import java.util.Stack;

public class Main {

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

		String s = sc.next();

		Stack<Character> stack = new Stack<Character>();

		for(int i = 0; i < s.length(); i++){
			char c = s.charAt(i);

			switch(c){
			case '1':
			case '0':
				stack.push(c);
				break;
			case 'B':
				if(!stack.isEmpty()){
					stack.pop();
				}
			}
		}

		String result = "";
		while(!stack.isEmpty()){
			result = stack.pop() + result;
		}

		System.out.println(result);
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
const int MOD = 1000000007;
const int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
typedef pair<int,pair<int, int>> P1;

using Graph = vector<vector<int>>;

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  int ans = 0;
  rep(i,N+1) ans += i;
  cout << ans << endl;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

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

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;

ll MOD = 1e9+7;


template <typename T>
class Rerooting{
public:
	vector<vector<int>> edge;
	vector<map<int,T>> memo;
	vector<map<int,T>> sumL;
	vector<map<int,T>> sumR;

	struct Solver {
		virtual T init() const = 0;
		virtual T merge(T, T) const = 0;
		virtual T add_me(T) const = 0;
	};
	const Solver *solver;

	const T init_value;

	Rerooting(
			int N,
			const Solver *solver
	) :
		edge(N),
		memo(N),
		sumL(N),
		sumR(N),
		solver(solver),
		init_value(solver->init())
	{ }

	void add_edge(int u, int v){
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	T solve(int n, int b = -1){
		if(memo[n].count(b)) return memo[n][b];

		if(b >= 0 && memo[b].count(n)){
			// b -> n が存在するとき、nが根のときの結果を使って高速化する
			solve(n, -1);  // sumL, sumR の計算がまだな場合は計算する
			// auto ret = solver->merge(sumL[n][b], sumR[n][b]);
			// return memo[n][b] = solver->add_me(ret);
			return memo[n][b];
		}

		T ret = init_value;
		for(auto t: edge[n]) if(t != b){
			ret = solver->merge(ret, solve(t, n));
		}

		if(b < 0){
			// nが根のときは、累積を計算しておく
			T sum = init_value;
			rep(i, edge[n].size()){
				int t = edge[n][i];
				sumL[n][t] = sum;
				sum = solver->merge(sum, solve(t,n));
			}
			sum = init_value;
			rrep(i, edge[n].size()){
				int t = edge[n][i];
				sumR[n][t] = sum;
				sum = solver->merge(sum, solve(t,n));
			}

			for(auto t: edge[n]) {
				auto ret = solver->merge(sumL[n][t], sumR[n][t]);
				memo[n][t] = solver->add_me(ret);
			}
		}

		return memo[n][b] = solver->add_me(ret);
	}
};

struct Solver: Rerooting<ll>::Solver {
	ll init() const override {
		return 1;
	}

	ll merge(ll a, ll b) const override {
		return a * b % MOD;
	}

	ll add_me(ll a) const override {
		return a + 1;
	}
};

int main(){
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N >> MOD;
	Rerooting<ll> rr(N, new Solver());
	rep(i,N-1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		rr.add_edge(a, b);
	}

	rep(i,N) cout << rr.solve(i) - 1 << "\n";

	return 0;
}

Measured memory_bytes: 75776
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int nidx[N][27];

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	string s , t ;cin >> s >> t;
	int n = (int)s.size() , m = (int)t.size();
	memset(nidx , -1 , sizeof nidx);
	nidx[n - 1][s[n - 1] - 'a'] = n - 1;
	for(int i = n - 2 ;i >= 0 ; i -- ){
		for(int j = 0 ; j <= 26 ; j ++ ) nidx[i][j] = nidx[i + 1][j];
		nidx[i][s[i] - 'a'] = i;
	} 
	long long ans = 0;
	int j = 0 , i = 0;
	set<char> a , b;
	for(char k : s) a.insert(k);
	for(char k : t) b.insert(k);
	for(char k: b) {
		if(a.find(k) == a.end()) {
			cout << -1;
			return 0;
		}
	}
	while(j < m) {
		if(nidx[i][t[j] - 'a'] == -1) {
			ans ++ ;
			i = 0;
		} else {
			int pos = nidx[i][t[j] - 'a'];
			i = pos + 1;
			j ++;
		}
	}
	cout << ans*n + i;
			
}


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

n = INT()
m = [int(i) for i in str(n)]
l = len(m)
dp = [[0, 0] for _ in range(l)]
dp[0][0] = m[0] - 1
dp[0][1] = m[0]
for i in range(1, l):
    dp[i][0] = max(dp[i - 1][0] + 9, dp[i - 1][1] + m[i] - 1)
    dp[i][1] = dp[i - 1][1] + m[i]
print(max(dp[l - 1][0], dp[l - 1][1]))

Measured memory_bytes: 5264
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N;
  cin >> N;
  long long ans = 0;
  long long sum_vec = 0;

  vector<long long> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    ans += sum_vec * A.at(i);
    ans %= 1000000007;

    sum_vec += A.at(i);
    sum_vec %= 1000000007;

  }

  cout << ans << endl;
}

Measured memory_bytes: 4816
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int main()
{
	int n = 0, k = 0;
	scanf("%d %d", &n, &k);
	
	int arr[1001] = { 0 };
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < k; i++)
	{
		sum += arr[i];
	}
	printf("%d\n", sum);
	


	return 0;

}

Measured memory_bytes: 1696
def gcd(x, y):
  if x % y == 0:
    return y
  
  return gcd(y, x % y)


K = int(input())
count = 0

# a, b, cが全て一致する場合
count += K * (K+1) / 2

# a, b, cのうち、いずれか二つが一致する場合
for a in range(1, K):
  for b in range(a+1, K+1):
    count += gcd(b, a) * 6

# a, b, cが全て異なる場合
for a in range(1, K-1):
  for b in range(a+1, K):
    ab = gcd(b, a)
    
    for c in range(b+1, K+1):
      count += gcd(c, ab)  * 6

print(int(count))

Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define strall(v) (v).cbegin(),(v).cend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
//const long long INF = 1LL << 60;
 int INF = 500000;
 int MAX = 2050;
 ll mod = 1e9+7;


int main(){
  int k,x;
  cin >> k >> x;
  int start = x-(k-1);
  int end = x+(k-1);
  for(int i=start;i<=end;i++){
    cout << i <<((i == end) ? "\n":" ");
  }  
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int x;
int d(int k) {
    int t = k * (k + 1) / 2;
    if(x <= t) return true;
    else return false;
}

signed main() {
    cin >> x;
    int ub = (int)1e9, lb = -1;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(d(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}

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

int main()
{
    int n;
    while(cin >> n && n) {
        vector<vector<int> > vs;
        vs.resize(2);
        vs[0].resize(n); vs[1].resize(n);
        for(int i = 0; i < n; i++)
            cin >> vs[0][i];

        sort(vs[0].begin(), vs[0].end());
        for(int i = 1, j = 0; i <= 2 * n; i++)
            if(find(vs[0].begin(), vs[0].end(), i) == vs[0].end())
                vs[1][j++] = i;

        int field = -1, turn = 0;
        while(vs[0].size() != 0 && vs[1].size() != 0) {
            if(field == -1) {
                field = vs[turn][0];
                swap(vs[turn][0], vs[turn][vs[turn].size() - 1]);
                vs[turn].resize(vs[turn].size() - 1);
                sort(vs[turn].begin(), vs[turn].end());
            } else {
                bool ok = false;
                for(int i = 0; i < vs[turn].size(); i++) {
                    if(vs[turn][i] > field) {
                        field = vs[turn][i];
                        swap(vs[turn][i], vs[turn][vs[turn].size() - 1]);
                        vs[turn].resize(vs[turn].size() - 1);
                        sort(vs[turn].begin(), vs[turn].end());
                        ok = true;
                        break;
                    }
                }
                if(!ok)
                    field = -1;
                    
            }
            turn = (turn + 1) % 2;
        }
        cout << vs[1].size() << endl << vs[0].size() << endl;
            
    }
}

Measured memory_bytes: 0
string = list(input())
q = int(input())

def print_func(head, end):
    string_p = ''
    for i in range(head,end + 1):
        string_p += string[i]
    print(string_p)

def reverse_func(head, end):
    i = 0
    while head + i <= end - i:
        string[head + i],string[end - i] = string[end - i],string[head + i]
        i += 1

def replace_func(head, end, r_str):
    l_r_str = list(r_str)
    for i in range(end - head + 1):
        string[head + i] = l_r_str[i]

for i in range(q):
    l = list(input().split())
    l[1] = int(l[1]); l[2] = int(l[2])
    if l[0] == 'print':
        print_func(l[1],l[2])
    elif l[0] == 'reverse':
        reverse_func(l[1],l[2])
    else:
        replace_func(l[1],l[2],l[3])


Measured memory_bytes: 5624
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )
static const int N_MAX = 100000;
static const int NINF = -1000000000;
int N, P[N_MAX], ans;
int dp[N_MAX][3];
vector<int> T[N_MAX];
bool V[N_MAX];

void dfs(int u){
  V[u] = true;
  vector<int> C;
  rep (i, T[u].size()){
    int v = T[u][i];
    if ( !V[v] ) {
      C.push_back(v);
      dfs(v);
    }
  }

  if ( C.size() == 0 ){
    rep(i, 3) dp[u][i] = P[u];
  } else if ( C.size() == 1 ){
    int v = C[0];
    dp[u][0] = max(dp[v][0] - 1 + P[u], P[u]);
    dp[u][1] = max(dp[v][1] - 2 + P[u], P[u]);
    dp[u][2] = max(dp[v][2] - 2 + P[u], P[u]);
  } else {
    int a1, a2, c1;
    a1 = a2 = c1 = C[0];
    rep (i, C.size()){
      int v = C[i];
      if ( dp[a1][0] - 1 - max(dp[a1][1] -  2, 0) <= dp[v][0] - 1 - max(dp[v][1] - 2, 0) ) a1 = v;
      if ( dp[c1][2] - 2 - max(dp[c1][1] -  2, 0) <= dp[v][2] - 2 - max(dp[v][1] - 2, 0) ) c1 = v;
    }
    rep(i, C.size()) if ( C[i] != a1 ) { a2 = C[i]; break; }
    rep(i, C.size()){
      int v = C[i];
      if ( v == a1 ) continue;
      if ( dp[a2][0] - 1 - max(dp[a2][1] -  2, 0) <= dp[v][0] - 1 - max(dp[v][1]  - 2, 0) ) a2 = v;
    }
    int sumA1 = 0;
    int sumB1 = 0;
    int sumC1 = 0;
    int sumC2 = 0;
    for ( int i = 0; i < C.size(); i++ ){
      int v = C[i];
      sumA1 += (v == a1) ? (dp[v][0] - 1) : max(dp[v][1] - 2, 0);
      sumB1 += max(dp[v][1] - 2, 0);
      sumC1 += (v == c1) ? (dp[v][2] - 2) : max(dp[v][1] - 2, 0);
      sumC2 += (v == a1 || v == a2) ? (dp[v][0] - 1) : max(dp[v][1] - 2, 0);
    }
    int sumA = sumA1;
    int sumC = max(sumC1, sumC2);
    int sumB = sumB1;
    dp[u][0] = max(P[u], sumA + P[u]);
    dp[u][1] = max(P[u], sumB + P[u]);
    dp[u][2] = max(P[u], sumC + P[u]);
  }
  rep(i, 3) ans = max(ans, dp[u][i]);
}

int solve(int s){
  rep(i, N) rep(j, 3) dp[i][j] = NINF;
  rep(i, N) V[i] = false;
  ans = NINF;
  dfs(s);
  return ans;
}

int main(){
  cin >> N;
  for ( int i = 0; i < N; i++ ) cin >> P[i];
  for ( int i = 0; i < N - 1; i++ ) {
    int s, t; cin >> s >> t;
    s--; t--;
    T[s].push_back(t);
    T[t].push_back(s);
  }

  int a = solve(0);
  cout << a << endl;

  return 0;
}


Measured memory_bytes: 25896
#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int main(void)
{
    int q1, b, c1, c2, q2;

    while (scanf("%d %d %d %d %d", &q1, &b, &c1, &c2, &q2), q1){
        int jidori = min(b / c1, q2);
        int chicken = (b - c1 * jidori) / c2;
        int remain = q1 - jidori - chicken;

        b -= jidori * c1 + chicken * c2;
        while (c1 > c2 && jidori > 1 && remain > 0){
            jidori--;
            b += c1;
            chicken += b / c2;
            remain -= b / c2 - 1;
            b %= c2;
        }

        if (jidori + chicken < q1 || jidori == 0){
            puts("NA");
        }
        else {
            printf("%d %d\n", jidori, chicken);
        }
    }

    return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define all(v) v.begin(), v.end()
bool chmin(ll& a, ll b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
bool chmax(ll& a, ll b) {
    if (b > a) {
        a = b;
        return 1;
    }
    return 0;
}
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans, s;
int main() {
    vl A,ANS(MAX_N);
    cin >> n;
    A.push_back(0);
    rep(i, n) {
        cin >> x;
        A.push_back(x);
    }
    A.push_back(0);
    n+=2;
    vl X(n,0),Y(n,0);

    deque<PP> DQ;

    rep(i, n) {
        while (!DQ.empty() && DQ.back().second > A[i]){
            X[DQ.back().first] += i - DQ.back().first;
            DQ.pop_back();
        }
        DQ.push_back({i, A[i]});
    }
    

    reverse(all(A));

    DQ.clear();

    rep(i, n) {
        while (!DQ.empty() && DQ.back().second > A[i]){
            Y[DQ.back().first] += i - DQ.back().first;
                    DQ.pop_back();
        }
        DQ.push_back({i, A[i]});
    }
    
	
    reverse(all(Y));
    reverse(all(A));

    rep(i, n) { ANS[i] = X[i] + Y[i]-1;
        ans = max(ans, ANS[i] * A[i]);
    }
    

    cout << ans << endl;
}


Measured memory_bytes: 10740
#include <iostream>
#include <fstream>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef __int128 lll;
constexpr ll mod = 1000000007;

int main() {
    int n, x;
    cin >> n >> x;
    if (n == 2) {
        if (x == 2) cout << "Yes" << endl << 1 << endl << 2 << endl << 3 << endl;
        else cout << "No" << endl;
    } else if (x == 1 || x == 2*n - 1) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        if (x == 2) {
            int c = 1, o[4] = {1, 0, -1, 2};
            for (int i = 1; i < 2 * n; i++) {
                if (i < n - 1 || i > n + 2) {
                    while (c >= x - 1 && c <= x + 2) c++;
                    cout << c << endl;
                    c++;
                } else {
                    cout << x + o[i - (n - 1)] << endl;
                }
            }
        } else {
            int c = 1, o[4] = {-1, 0, 1, -2};
            for (int i = 1; i < 2 * n; i++) {
                if (i < n - 1 || i > n + 2) {
                    while (c >= x - 2 && c <= x + 1) c++;
                    cout << c << endl;
                    c++;
                } else {
                    cout << x + o[i - (n - 1)] << endl;
                }
            }
        }
    }
}

Measured memory_bytes: 1536