akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double E = 1e-9;
//int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0 ,1, 1, 1, 0, -1, -1, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
int n, W;
ll w[101];
int v[101];
ll dp[101][N];
ll f(int i, int want){
    if(want < 0)return 1e18;
    if(i == n)return want == 0 ? 0 : 1e18;
    ll &ans = dp[i][want];
    if(ans == -1){
        ans = 1e18;
        ans = min(f(i + 1, want), ans);
        ans = min(ans, f(i + 1, want - v[i]) + w[i]);

    }return ans;
}
int main(){
    //FL;
    FIN;
    cin >> n >> W;
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i] >> v[i];
        sum += v[i];
    }
    for(int i = n; i >= 0; i--){
        for(int want = 0; want <= sum; want++){// hast limite sumaMAx
            ll &ans = dp[i][want];
            if(i == n){
                ans = want == 0 ? 0 : 1e18;
                continue;
            }
            ans = 1e18;
            ans = min(ans, dp[i + 1][want]);
            if(want - v[i] >= 0)
                ans = min(ans, dp[i + 1][want - v[i]] + w[i]);
        }
    }
    int ans = 0;
    for(int i = 0; i < sum + 1; i++){
        ll cur = dp[0][i];
        if(cur <= W)
            ans = i;
    }
    cout << ans << '\n';
    EjecuteTime;
    return 0;
}       

Measured memory_bytes: 82640
#include <bits/stdc++.h>
using namespace std;
using sint = int64_t;

template<class T> T read() {
	T t;
	cin >> t;
	return t;
}

template<> string read<string>() {
	string s;
	getline(cin, s);
	return s;
}

inline void write() {
}

template<class T> void write(T const& t) {
	cout << t;
}

template<class T, class... Args> void write(T const& t, Args const&... args) {
	cout << t << ' ';
	write(args...);
}

template<class... Args> void writeln(Args const&... args) {
	write(args...);
	cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin .exceptions(ios_base::badbit | ios_base::failbit);
	cout.exceptions(ios_base::badbit | ios_base::failbit);
	cin .tie(nullptr);
	cout.tie(nullptr);
	cout.precision(16);
	void run();
	run();
	return 0;
}

void run() {
	auto const N = read<sint>();
	vector<sint> As;
	for (sint i = 0; i < N; ++i) {
		As.push_back(read<sint>());
	}
	sint sum = 0;
	for (sint i = 0; i < N; ++i) {
		sum += read<sint>();
	}
	vector<sint> Cs;
	for (sint i = 1; i < N; ++i) {
		Cs.push_back(read<sint>());
	}

	for (sint i = 1; i < N; ++i) {
		if (As[i - 1] + 1 == As[i]) {
			sum += Cs[As[i - 1] - 1];
		}
	}

	writeln(sum);
}

Measured memory_bytes: 256
def card_print(mark, cards):
    for i in range(1, 14):
        pair = [mark, str(i)]
        if not pair in cards:
            print(" ".join(pair))

n = int(input())
cards = []
while True:
    if n <= 0:
        break
    cards.append(input().split())
    n -= 1
card_print("S", cards)
card_print("H", cards)
card_print("C", cards)
card_print("D", cards)






Measured memory_bytes: 5596
import sys

score = []
while (True):
    lst = list(map(int, input().split(' ')))
    if lst[0] == -1 and lst[1] == -1 and lst[2] == -1:
        break
    score.append(lst)


for item in score:
    if item[0] == -1 or item[1] == -1:
        print("F")
    elif 80 <= item[0] + item[1]:
        print("A")
    elif 65 <= item[0] + item[1] and item[0] + item[1] < 80:
        print("B")
    elif 50 <= item[0] + item[1] and item[0] + item[1] < 65:
        print("C")
    elif 30 <= item[0] + item[1] and item[0] + item[1] < 50:
        if 50 <= item[2]:
            print("C")
        else:
            print("D")
    else:
        print("F")



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

int main(){
char s[4]; int k=0;
scanf("%s\n",s);
for(int i=1; i<4; i++){
if(s[i-1] == s[i]){
    printf("Bad\n");
    k++;
    break;
}
}
if(!k) printf("Good\n");
return 0;
}

Measured memory_bytes: 256
n,*l=map(int,open(0).read().split())
a,c=1000,0
for i in range(n-1):
  if l[i]>l[i+1]: a+=c*l[i]; c=0
  if l[i]<l[i+1]:
    t=a//l[i]; a-=t*l[i]; c+=t
print(a+c*l[n-1])

Measured memory_bytes: 9096
fn read_as_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim()
        .split_whitespace()
        .map(|e| e.trim().parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read_as_vec::<u16>();

    if n[0] > n[1] {
        println!("{}", "safe");
    } else {
        println!("{}", "unsafe");
    }
}


Measured memory_bytes: 2108
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

#define ISEQ(c) (c).begin(), (c).end()
typedef long long ll;

int main() {
  int m;
  cin >> m;
  for (int z = 0; z < m; z++) {
    int money, year, n;
    int maxi = 0;
    cin >> money >> year >> n;
    for (int i = 0; i < n; i++) {
      int k;
      double r;
      int f;
      int p = money;
      cin >> k >> r >> f;
      int intre = 0;
      for (int j = 0; j < year; j++) {
	double d = p * r;
	if (k) {
	  p += (int)d;
	} else {
	  intre += d;
	}
	p -= f;
      }
      maxi = max(maxi, p + intre);
    }
    cout << maxi << endl;
  }
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
void solve(){
string s0 ;
string s1 ;
int x;
int count = 0;

cin >> s0;
cin >> s1;

x = s0.length();


for (int i=0; i < x; i++)
{
  if(s0[i]!=s1[i]) { count = 1;  break;}
  
}


if(count == 0) {cout << "Yes";}
if(count == 1) {cout << "No";}

}

int main(){

	solve();
	return 0;

}

Measured memory_bytes: 3604
<?php
$input_line = trim(fgets(STDIN));
$array = [];
for ($i = 0; $i < $input_line; $i++) {
  $s = trim(fgets(STDIN));
  $s = str_replace(array("\r\n", "\r", "\n"), '', $s);
  $array[] = $s;
}

$max_value = max($array);
$max_key = array_search($max_value, $array);

for ($i = 0; $i < $input_line; $i++) {
  if ($i == $max_key) {
    unset($array[$i]);
    echo max($array) . "\n";
  } else {
    echo $max_value . "\n";
  }
}

Measured memory_bytes: 40308
#include<bits/stdc++.h>
	using namespace std;
	#define xxx ios::sync_with_stdio(),cin.tie(0),cout.tie(0)
	#define rep(i,n) for(int i=0;i<n;i++)
	#define int long long
	int bp(int a, int b, int m) {
   		a %= m;
   		int res = 1;
    	while (b > 0) {
        	if (b & 1)
            	res = res * a % m;
       		a = a * a % m;
       	 	b >>= 1;
 	    }
    return res;
	}
	int max(int a, int b){
		return (a>b)?a:b;	
	}
	int csb( int n) 
{ 
    int count = 0; 
    while (n) { 
        count += n & 1; 
        n >>= 1; 
    } 
    return count; 
} 
	int solve(int x){
		int r=0;
		while(x>0){
			int t=csb(x);
			x%=t;
			r++;
		}
		return r;
	}

	signed main(){
		int test=1;
		//cin>>test;
		while(test--){
			int n;
			cin>>n;
			int a[n];
			rep(i,n) cin>>a[i];
			sort(a,a+n);
			int  s=0;
			//for(int i=0;i<n;i++){ cout<<a[i]<<" ";}
				//cout<<endl;
			rep(i,n){
				for(int j=i+1;j<n;j++){
					int lt=a[i]+a[j];
					int ind=upper_bound(a,a+n,lt-1)-a;
					if(ind==n) ind=n-1;
					if(ind<=j) continue;
					if  (a[ind]<lt){ s+=ind-j;}//cout<<i<<" "<<j<<" "<<ind<<endl;}
					else if(a[ind-1]<lt && ind-1 >j){ s+=ind-j-1;}//cout<<i<<" "<<j<<" "<<ind<<endl;}

				}
			}
			cout<<s<<endl;
		}
		return 0;
	}

Measured memory_bytes: 3648
#pragma region Imports
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
using namespace std;
#pragma endregion
#pragma region Macros
#pragma GCC optimize (2)
#define uns unsigned
#define out cout
#define in cin
#define au auto
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define elif else if
#define sz(x) x.size()
#define fl(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define fli(i, a, b, c) for(int (i)=a;(i)<(b);(i)+=(c))
#define fr(i, x) for(int (i)=(x)-1;(i)>=0;(i)--)
#define fb(i, x) for(int (i)=0;(i)<(x);(i)++)
#define fa(i, x) for(auto& (i):(x))
#define ia(a, n) for(int qw=0;qw<(n);qw++)cin>>(a)[qw];
#define oa(a, n) for(int qw=0;qw<(n);qw++)cout<<(a)[qw]<<" ";
#define im(a, n, m) fb(i,(n))fb(j,(m))cin>>(a)[i][j];
#define om(a, n, m) fb(i,(n))fb(j,(m))cout<<(a)[i][j]<<" \n"[j==(m)-1];
#define eb(v, x) (v).emplace_back(x);
#define seb(s, x) (s).emplace(x);
#define pr(x, y) pair<x,y>
#define vr(x) vector<x>
#define mp(x, y) make_pair(x,y)
#define hm(x, y) map<x,y>
#define um(x, y) unordered_map<x,y>
#define stk(x) stack<x>
#define qu(x) queue<x>
#define dq(x) deque<x>
#define pq(x) priority_queue<x>
#define pqm(x) priority_queue<x,vector<x>,greater<(x)>>
#define mem(a, x) memset(a,(x),sizeof(a));
#define fi(x) (x).first
#define se(x) (x).second
#define ql(x) int tc;tc=(x);if(tc==-1)cin>>tc;while(tc--)
#define srt(x) sort((x).begin(),(x).end());
#define pops(y, x) auto (y)=(x).front();(x).pop();
#define ppc(x) __builtin_popcount((x))
#define all(x) (x).begin(),(x).end()
#define sieve(b, n) bool (b)[(n)];mem((b),true);int sq=int(sqrt(n))+1;(b)[0]=(b)[1]=false;fl(i,2,sq)if((b)[i])fli(j,i*i,n,i)(b)[j]=false;
#define dbg(x) cout<<#x<<" "<<(x)<<"\n";
#pragma endregion
#pragma region Typedefs and Consts
typedef long long int ll;
typedef unsigned long long int ull;
typedef string stg;
typedef float flo;
typedef char chr;
typedef vector<int> vi;
const ull mod = 1000000007;
const int imx = INT_MAX;
const int imn = INT_MIN;
const ll lmx = LLONG_MAX;
const ll lmn = LLONG_MIN;
#pragma endregion
#pragma region Functions
inline ull powm(ull x,ull y,bool b=false,ull m=mod){ if(b){ ull t=1;x%=m;while(y>0){ if(y%2)t=(t*x)%m;y=y>>1;x=(x*x)%m; }return t; }else
    { ull t=1;while(y>0){ if(y&2)t*=x;y=y>>1;x*=x; }return t;}}
inline ll gcd(ll a,ll b){a=abs(a);b=abs(b); while(b!=0){ ll c=a%b;a=b;b=c;}return a;}
#pragma endregion

//cout<<"Case #"+to_string(tc+1)+": "+to_string(z)<<endl;
ll d[10001][101][2];
ll f(int a[],int n,int r,int i,int s,bool e){
  if(i==n)
    return s==0;
  if(d[i][s][e]==-1){
    ll z=0;
    if(e)
      fb(j,a[i]+1)
      z=(z+f(a,n,r,i+1,(s+j)%r,e and j==a[i]))%mod;
   	else
      fb(j,10)
      z=(z+f(a,n,r,i+1,(s+j)%r,e and j==a[i]))%mod;
    d[i][s][e]=z;
  }
  return d[i][s][e];
}
int main() {
  fio
  string s;
  in>>s;
  int r,n=sz(s);
  in>>r;
  int a[n];
  fb(i,n)
    a[i]=s[i]-'0';
  fb(i,10001)
    fb(j,101)
    	d[i][j][0]=d[i][j][1]=-1;
  out<<(f(a,n,r,0,0,true)-1+mod)%mod;
  return 0;
}


Measured memory_bytes: 16896
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	double a;
	while(cin >> a){
		double ans = a;
		for(int i = 2; i <= 10; i++){
			if(i%2==0){
				ans += a = a*2;
			}
			else{
				ans += a = a/3;
			}
		}
		printf("%.8lf\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1236
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e20);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a>b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a<b ? : a = b; }



int main() {
    int N, K;
    vint H;
    cin >> N >> K;
    rep(i, N) {
        int h;
        cin >> h;
        H.push_back(h);
    }

    vint dp(N, INF);
    dp[0] = 0;
    rep(i, N) {
        REP(k, 1, K+1) {
            if (i + k < N)
                dp[i + k] = min(dp[i + k], dp[i] + abs(H[i] - H[i + k]));
        }
    }
    cout << dp[N - 1] << endl;

    return 0;
}

Measured memory_bytes: 1144
#include "stdio.h"

int main (void){
	int W, a, b;
	scanf("%d %d %d", &W, &a, &b);
	if(b > a + W){printf("%d\n",b - (a+W));}
	else if(a > b + W){printf("%d\n",a - (b+W));}
	else {printf("0\n");}
	return 0;
}

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

typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  map<int,int> m;
  for(int i=0; i<N; i++){
    cin >> A[i];
    m[A[i]%2]++;
  }

  if(m[1]%2==0) cout << "YES" << endl;
  else cout << "NO" << endl;

}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline
MOD=10**9+7
n=int(input())
l=list(map(int,input().split()))
lc=[0]*(n+1)
ans=1
tmp=3
for i in l:
    if i==0:
        ans*=tmp
        ans%=MOD
        tmp-=1
    else:
        ans*=lc[i-1]
        ans%=MOD
        lc[i-1]-=1
    lc[i]+=1
print(ans)

Measured memory_bytes: 14408
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <cstring>
using namespace std;

const int nlimit = 105;

int n;
vector<int> graph[2*nlimit];
int match[2*nlimit];
bool used[2*nlimit];

bool dfs(int);
int mathcing();

int main(){
  cin >> n;
  pair<int, int> r[n+1], b[n+1];

  int x, y;
  for(int i=1; i<=n; i++){
    cin >> x >> y;
    r[i] = make_pair(x, y);
  }
  for(int i=1; i<=n; i++){
    cin >> x >> y;
    b[i] = make_pair(x, y);
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      if(r[i].first<b[j].first && r[i].second<b[j].second){
        graph[i].push_back(n+j);
        graph[n+j].push_back(i);
      }
    }
  }

  int ans = mathcing();

  cout << ans << endl;

  return 0;
}

bool dfs(int v){
  used[v] = true;
  for(int i=0; i<graph[v].size(); i++){
    int u=graph[v][i], w = match[u];
    if(w < 0 || !used[w] && dfs(w)){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int mathcing(){
  int res=0;
  memset(match, -1, sizeof(match));
  for(int v=1; v<=n; v++){
    if(match[v]<0){
      memset(used, 0, sizeof(used));
      if(dfs(v)) res++;
    }
  }
  return res;
}


Measured memory_bytes: 256
#include <stdio.h>

using namespace std;

int main() {
  int A,B,X;
  scanf("%d %d %d",&A,&B,&X);
  bool can = true;
  if (A > X) can = false;
  if (X > A + B) can = false;
  if (can) printf("YES\n");
  else printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
import scala.io.StdIn.{readLine,readInt}
/**
  * AOJ
  */

object Main {

  def main(args: Array[String]): Unit = {
    println(if(find(read,read)){"Yes"}else{"No"})
  }

  def find(dice1:Array[Int],dice2:Array[Int]) : Boolean = {
    for(i <- createDiceArray(dice1,"WNNNW"); j <- createDiceArray(i,"HHH")){
      if(diceMatch(j,dice2)){return true}
    }
    return false
  }

  def createDiceArray(dice:Array[Int],commands:String) : List[Array[Int]] = {
    var dices = List(dice)
    for(cmd <- commands.toCharArray){
      dices :+= getNextStatus(cmd,dices.last)
    }
    dices
  }

  def read() : Array[Int] = {readLine().split(" ").map(_.toInt)}

  def diceMatch(dice1:Array[Int],dice2:Array[Int]):Boolean = (dice1 zip dice2).forall(x => x._1 == x._2)

  def getNextStatus(cmd:Char,dice:Array[Int]): Array[Int] = {
    cmd match {
      case 'N' => Array(dice(1), dice(5), dice(2), dice(3), dice(0), dice(4))
      case 'H' => Array(dice(0), dice(2), dice(4), dice(1), dice(3), dice(5))
      case 'W' => Array(dice(2), dice(1), dice(5), dice(0), dice(4), dice(3))
    }
  }
}

Measured memory_bytes: 44240
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int sum = scanner.nextInt();
		int count = 0;
		
		int i = 0 , j = 0 , k = 0; 
		for(i = 0; i<=n ; i++){
			for(j = 0 ; j<=n ; j++){
				for(k = 0 ; k<=n ; k++){
					if(i+j+k<=sum){
						k = Math.min(n, sum-i-j);
						if(i+j+k<=sum-n){
							j = Math.min(n, sum-i-k);
							if(i+j+k<=sum-n){
								i = Math.min(n, sum-j-k);
							}
						}
					}else{
						break;
					}
					
					if( (i+j+k)==sum ) count++;
					//System.out.println("i="+i+" ,j="+j+" ,k="+k+" ,count="+count);
				}
			}
		}
		
		System.out.println(count);
	}
}
//2500 3000
//4128751

Measured memory_bytes: 23764
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define LL long long
#define MOD 1000000007
ll N, M, K,H,W, ans, mi, A;
string s;
int main() {
	cin >> H>>W;
	vector<vector<LL>> a(H,vector<LL>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> a[i][j];
		}
	}
	LL h, w;
	vector<pair<int, int>>c(H*W), b(H*W);
	LL num=0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W-1; j++) {
			if (a[i][j] % 2 == 1) {
				a[i][j]--;
				a[i][j + 1]++;
				b[num] = make_pair(i, j);
				c[num] = make_pair(i, j+1);
				num++;
			}
		}
	}

	for (int i = 0; i < H-1; i++) {
		if (a[i][W-1] % 2 == 1) {
			a[i][W-1]--;
			a[i+1][W-1]++;
			b[num] = make_pair(i, W - 1);
			c[num] = make_pair(i+1, W - 1);
			num++;
		}
	}
	cout << num << endl;
	for (int i = 0; i < num; i++) {
		cout << b[i].first+1 << " " << b[i].second+1 << " " << c[i].first+1 << " " << c[i].second+1 << endl;
	}
	return 0;

}



Measured memory_bytes: 7936
#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<ll,ll>;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}



int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    rep(i,n) {
        cin >> a[i] >> b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(n%2==0) {
        int sa=(a[n/2]+a[n/2-1]);
        int sb=(b[n/2]+b[n/2-1]);
        int ans=(sb-sa)+1;
        pt(ans);
    }
    else {
        int sa=a[(n-1)/2];
        int sb=b[(n-1)/2];
        int ans=(sb-sa)+1;
        pt(ans);
    }
    return 0;
}


Measured memory_bytes: 4840
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

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

    double ret = 0.0;
    multimap<double, pair<int, int> > mm;
    for(int i=0; i<n; ++i){
        int w, v;
        cin >> w >> v;
        if(w > 0){
            if(v > 0)
                mm.insert(make_pair(-v/(double)w, make_pair(w, v)));
        }else{
            wSum -= w;
            ret += v;
            if(v < 0)
                mm.insert(make_pair(-v/(double)w, make_pair(-w, -v)));
        }
    }

    while(!mm.empty()){
        int w = mm.begin()->second.first;
        int v = mm.begin()->second.second;
        mm.erase(mm.begin());

        if(w <= wSum){
            wSum -= w;
            ret += v;
        }else{
            ret += (double)v * wSum / w;
            wSum = 0;
        }
    }

    printf("%.10f\n", ret);
    return 0;
}

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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> h(n);
  for(int i=0; i<n; i++)cin>>h[i];

  vector<int> dp(n, 1000000000);

  dp[0]=0;
  for(int i=1; i<n; ++i){
    int x=max(0, i-k);
    for(int j=x; j<i; ++j)dp[i]=min(dp[i], dp[j]+abs(h[i]-h[j]));
  }

  cout<<dp[n-1]<<endl;
  

}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAX 100100
#define ll long long
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n,m,col[MAX],dis[MAX];
int Q,U[MAX],D[MAX],C[MAX];
void BFS(int S,int d,int c)
{
	if(dis[S]>=d)return;dis[S]=d;
	queue<int> Q;Q.push(S);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		if(!col[u])col[u]=c;
		if(!dis[u])continue;
		for(int i=h[u];i;i=e[i].next)
			if(dis[e[i].v]<dis[u]-1)
			{
				dis[e[i].v]=dis[u]-1;
				Q.push(e[i].v);
			}
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		Add(u,v);Add(v,u);
	}
	Q=read();memset(dis,-1,sizeof(dis));
	for(int i=1;i<=Q;++i)U[i]=read(),D[i]=read(),C[i]=read();
	for(int i=Q;i;--i)
		BFS(U[i],D[i],C[i]);
	for(int i=1;i<=n;++i)printf("%d\n",col[i]);
	return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <bitset>
#include <utility>
#include <queue>
#include <deque>

using namespace std;

int main(){

    constexpr int modulo = 998244353;
    int N, S;
    cin >> N >> S;
    int a, r, t;
    int tmp[3][2];
    vector<vector<vector<int>>> dp(3010, vector<vector<int>>( 3010, vector<int>(3, 0)));

    cin >> a;
    for(r=0;r<=S;++r){
        for(t=0;t<3;++t){
            if(r==0) dp[0][r][t] = 1;
            if(r <= S and r==a) dp[0][r][t] = 1;
        }       
    }
    
    for(int i=0;i<N-1;++i){
        cin >> a;
        for(r=0;r<=S;++r){
            // aを選ばない 
            tmp[0][0] = dp[i][r][0];

            if(r==0) tmp[1][0] = (dp[i][r][1] + 1) % modulo;
            else tmp[1][0] = dp[i][r][1];

            tmp[2][0] = (dp[i][r][2] + tmp[1][0]) % modulo;

            for(t=0;t<3;++t){
                dp[i+1][r][t] = (dp[i+1][r][t] + tmp[t][0]) % modulo;
            }

            // aを選ぶ 
            if(r+a > S) continue;
            tmp[0][1] = dp[i][r][0];

            if(r==0) tmp[1][1] = (dp[i][r][1] + 1) % modulo;
            else tmp[1][1] = dp[i][r][1];

            tmp[2][1] = tmp[1][1];

            for(t=0;t<3;++t){
                dp[i+1][r+a][t] = (dp[i+1][r+a][t] + tmp[t][1]) % modulo;
            }

        }
    }

    // for(int i=0;i<N;++i){
    //     for(r=0;r<=S;++r){
    //         for(t=0;t<3;++t){
    //             printf("dp[%3d][%3d][%d] = %d\n", i, r, t, dp[i][r][t]);
    //         }
    //     }
    // }

    cout << dp[N-1][S][2] << endl;
    
    return 0;
}


Measured memory_bytes: 496128
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE CPP               #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections     #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString             as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.HashMap.Strict         as M
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    !n <- readLn :: IO Int
    bs <- B.getLine
    print $ solve n bs

solve :: Int -> B.ByteString -> Int
solve n bs = sum [M.lookupDefault 0 pair rightFreq| pair<-lefts]
  where
    (left, right) = B.splitAt n bs
    lefts = pairs n left
    rights = map swap . pairs n $ B.reverse right
    !rightFreq = foldl' (\m pair -> M.insertWith (+) pair 1 m) M.empty rights

pairs :: Int -> B.ByteString -> [(B.ByteString, B.ByteString)]
pairs n bs = [divide i bs|i<-[0..2^n-1]]
  where
    divide :: Int -> B.ByteString -> (B.ByteString, B.ByteString)
    divide i bs = (xs, ys)
      where
        (xis, yis) = partition (testBit i) [0..n-1]
        !xs = B.pack $ map (B.unsafeIndex bs) xis
        !ys = B.pack $ map (B.unsafeIndex bs) yis



Measured memory_bytes: 153596
/* ちょっと参考にしたものあり */

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

class Program
{
    static long INF = 1000000001;
    static long cnt = 0;
    static void Merge(long[] A, int left, int mid, int right)
    {
        int n1 = mid - left;
        int n2 = right - mid;
        long[] B = new long[n1 + 1];
        long[] C = new long[n2 + 1];
        for (int i = 0; i < n1; i++) B[i] = A[left + i];
        for (int i = 0; i < n2; i++) C[i] = A[mid + i];
        B[n1] = INF;
        C[n2] = INF;
        int f1 = 0, f2 = 0;
        for (int k = left; k < right; k++)
        {
            if (B[f1] <= C[f2])
            {
                A[k] = B[f1];
                f1++;
            }
            else
            {
                A[k] = C[f2];
                f2++;
                cnt += (n1 - f1);
            }
        }
    }

    static void MergeSort(long[] A, int left, int right)
    {
        if (left + 1 < right)
        {
            int mid = (left + right) / 2;
            MergeSort(A, left, mid);
            MergeSort(A, mid, right);
            Merge(A, left, mid, right);
        }
    }

    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        long[] S = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        MergeSort(S, 0, n);
        Console.WriteLine(cnt);
    }
}


Measured memory_bytes: 48148
from collections import deque

def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()


Measured memory_bytes: 36864
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n, W;
int weight[110], value[110];

int dp[110][10010];

int main() {
	cin >> n >> W;
	for (int i = 0; i < n; ++i) cin >> value[i] >> weight[i];
	
	for (int w = 0; w <= W; ++w) dp[0][w] = 0;
	
	for (int i = 0; i < n; ++i) {
		for (int w = 0; w <= W; ++w) {
			if (w >= weight[i]) dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
			else dp[i + 1][w] = dp[i][w];
		}
	}
	
	cout << dp[n][W] << endl;
}



Measured memory_bytes: 7056
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define what_is(x) cerr << #x << " is " << x << endl;
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int INF = 1000000001;
const int MOD = 1000000007;
const int MAXN = 200000;

int n;
int digits[20];

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  cin >> n;
  int len;
  int ans = 0;
  for(len = 0; n; len++, n/=10) {
  	digits[len] = n%10;
  	ans += n%10;
  }
  len--;
  ans = max(ans, (digits[len]-1) + (len*9));
  cout << ans << endl;

}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<ll> a;

vector<vector<ll>> w;

ll dfs(ll k){
    vector<ll> depth(w[k].size());
    for(int i=0;i<w[k].size();i++){
        depth[i]=dfs(w[k][i]);
    }
    sort(depth.begin(),depth.end(),greater<ll>());
    ll mx=0;
    for(int i=0;i<w[k].size();i++){mx=max(mx,depth[i]+i+1);}
    return mx;
}


int main(){
    ll n;
    cin>>n;
    a.resize(n);
    w.resize(n);
    for(int i=1;i<n;i++){cin>>a[i]; a[i]--; w[a[i]].push_back(i);}
    cout<<dfs(0)<<endl;
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 14336
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split(" ");
	const S = parseInt(input[0]);
  const W = parseInt(input[1]);

  const ret = (S <= W)? 'unsafe' : 'safe';
  console.log(ret);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29400
a,b = map(int,input().split())
a1=(a*100)//8
if (a*100)%8!=0:
    a1+=1
a2=(a+1)*100//8
b1=b*10
b2=(b+1)*10




for i in range(1,1250):
    if a1<=i<a2 and b1<=i<b2:
        print(i)
        exit()

print(-1)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second





int main() {
	int n, k, a[100010], it, ans = 10000090;
	cin >> n >> k;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (a[i] == 1)it = i;
	}
	for (int i = it - k + 1;i <= it;i++) {
		if (i < 0)continue;
		int r = i + k - 1;
		if (r >= n)continue;
		ans = min(ans, (i + k - 2) / (k - 1) + (n - 1 - r + k - 2) / (k - 1) + 1);
	}

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

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

   private static final String INPUT_FILE_PATH = "";

   static int[] spf;
   static boolean[] composite;

   static void sieve(int n) {
      int sqrtN = (int) Math.sqrt(n);
      for (int i = 2; i <= sqrtN; i++) {
         if (composite[i]) continue;
         spf[i] = i;
         for (int j = i * i; j <= n; j += i) {
            composite[j] = true;
            if (spf[j] == 0) spf[j] = i;
         }
      }
      for (int i = sqrtN + 1; i <= n; i++) {
         if (!composite[i]) spf[i] = i;
      }
   }

   static int numDivisors(int i) {
      int res = 1;
      while (i > 1) {
         int p = spf[i];
         int pow = 0;
         while (i % p == 0) {
            pow++;
            i /= p;
         }
         res *= (pow + 1);
      }
      return res;
   }

   static void solve(InputReader in, PrintWriter out) {
      int n = in.nextInt();

      spf = new int[n + 1];
      composite = new boolean[n + 1];

      spf[1] = 1;
      sieve(n);

      long ans = 0;
      for (int i = 1; i <= n; i++) {
         ans += ((long) i) * numDivisors(i);
      }
      out.println(ans);
   }

   private static class InputReader {
      private BufferedReader br;
      private StringTokenizer st;

      public InputReader(InputStream inputStream) {
         this.br = new BufferedReader(new InputStreamReader(inputStream), 32768);
         this.st = null;
      }

      public String nextToken() {
         while (st == null || !st.hasMoreTokens()) {
            try {
               st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
               throw new RuntimeException(e);
            }
         }
         return st.nextToken();
      }

      public int nextInt() {
         return Integer.parseInt(nextToken());
      }

      public long nextLong() {
         return Long.parseLong(nextToken());
      }

      public double nextDouble() {
         return Double.parseDouble(nextToken());
      }
   }

   public static void main(String[] args) throws Exception {
      InputStream inputStream = INPUT_FILE_PATH.isEmpty()
         ? System.in
         : new FileInputStream(new File(INPUT_FILE_PATH));
      OutputStream outputStream = System.out;

      InputReader inputReader = new InputReader(inputStream);
      PrintWriter printWriter = new PrintWriter(outputStream);

      solve(inputReader, printWriter);

      printWriter.close();
   }

}


Measured memory_bytes: 82684
#include<stdio.h>
#include<math.h>
struct P{double x,y,z;};
#define S(x) ((x)*(x))
double D(P a,P b){return sqrt(S(a.x-b.x)+S(a.y-b.y)+S(a.z-b.z));}
int G(double x,double y)
{
	return (x*0.9998<=y&&y<=x*1.0002);
}
int F(P p,P q)
{
	double c=q.x/p.x,d=q.y/p.y,e=q.z/p.z;
	return G(c,d)&&G(c,e);
}
int main()
{
	P p,a[100];
	int T,n,i,j,k;
	for(scanf("%d",&T);T--;)
	{
		scanf("%lf%lf%lf%d",&p.x,&p.y,&p.z,&n);
		for(i=0;i<n;++i)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);
		for(i=0;i<n;++i)for(j=0;j<n;++j)for(k=0;k<n;++k)
		{
			if(i==j||j==k)continue;
			P x={D(a[j],a[k]),D(a[k],a[i]),D(a[i],a[j])};
			if(F(p,x))printf("%d %d %d\n",i+1,j+1,k+1);
		}
	}
	return 0;
}

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

#include <math.h>
#include <stdlib.h>


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

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

// const int INF = 1001001001;
// long long max => LLONG_MAX

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n, m; cin >> n >> m;

    ll ans;
    if(2 * n > m) ans = m / 2;
    else{
        ans = n;
        m -= 2 * n;
        ans += m/4;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld double
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pll pair <ll,ll>
#define nl "\n"
ld dp[3002][3002],ans;
int main()
{
	ios_base::sync_with_stdio(false);
	ll n,i,j;
	cin>>n;
	ld h[n+2],t[n+2];
	for(i=0;i<n;i++)
	{
		cin>>h[i];
		t[i]=1-h[i];
	}
	dp[0][1]=h[0];
	dp[0][0]=t[0];
	for(i=1;i<n;i++)
	{	
		dp[i][0]=dp[i-1][0]*t[i];
		for(j=1;j<=i+1;j++)
		{
			dp[i][j]=dp[i-1][j-1]*h[i]+dp[i-1][j]*t[i];
		}
	}
	for(i=n/2+1;i<=n;i++)
		ans+=dp[n-1][i];
	printf("%.11lf\n",ans);
	return 0;
}

Measured memory_bytes: 68992
#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()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
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 int INF = 1e9+5;


int main(){
  int n;cin >> n;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  vector<int> dp(n+5,INF);
  dp[0] = 0;
  dp[1] = abs(h[1]-h[0]);
  for(int i=2;i<n;i++){
     dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
     dp[i] = min(dp[i],dp[i-2] + abs(h[i]-h[i-2]));   
  }
  cout << dp[n-1] << endl;
} 

Measured memory_bytes: 1024
def f(n):
    n = list(map(int, str(n)))
    if len(n) == 1:
        print(n[0])
    else:
        if sum([x - 9 for x in n]) != 0:
            mx = 9 * (len(n)-1) + n[0] - 1
        else:
            mx = 9 * len(n)
        print(max(mx, sum(n)))

n = int(input())
f(n)


Measured memory_bytes: 9096
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
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; }
const int INF = 1e9;
const ll MOD = 1000000007;

using Graph = vector<vector<int>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    ll res = 1000000000010;
    ll tmp = 0;
    for(ll i=1; i*i<=n; ++i) {
        if (n%i == 0) {
            tmp = (i-1)+(n/i)-1;
            res = min(tmp, res);
        }
    }
    cout << res << "\n";
}



Measured memory_bytes: 256
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
 
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		String c=s.next();
		if(n%2==1)
		System.out.println("No");
		else
		{String a=c.substring(0,n/2);
		String b=c.substring(n/2,n);
		if(a.equals(b))
		System.out.println("Yes");
		else
		System.out.println("No");}}}

Measured memory_bytes: 23124
import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)

Measured memory_bytes: 75772
S=input()
l=len(S)

if l <=25:
    for i in range(26):
        ch=chr(ord('a')+i)
        if ch not in S:
            S+=ch
            break
elif S=='zyxwvutsrqponmlkjihgfedcba':
    S=-1
else:
    index=24
    tmp=[ord(S[25])]
    while ord(S[index]) > ord(S[index+1]):
        tmp.append(ord(S[index]))
        index -= 1

    re=max(tmp)
    for ch in tmp:
        if ch < re and ch > ord(S[index]) :
            re = ch
    S=S[:index]+chr(re)

print(S)

Measured memory_bytes: 3064
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for (ll i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;
TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM K, TNM V> using umap = unordered_map<K, V>;
TPL<TNM K, TNM V> using uset = unordered_set<K, V>;

TPL<class T> inline void OUT(const T &x) { cout << x << "\n"; }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }

int main(void) {
	string S;
	cin >> S;
	int ans = 0;
	REP(i, 4) {
		if (S[i] == '+')++ans;
		else --ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
S = [None] * N
for i in range(N):
    S[i] = input()

print("AC x " + str(S.count("AC")))
print("WA x " + str(S.count("WA")))
print("TLE x " + str(S.count("TLE")))
print("RE x " + str(S.count("RE")))

Measured memory_bytes: 16096
x1,y1,x2,y2 = map(int,input().split())

side_x=x2-x1
side_y=y2-y1

pattern = [[side_x,side_y],[-side_y,side_x],[-side_x,-side_y],[side_y,side_x]]*2

i = pattern.index([side_x,side_y])
x3,y3 = x2+pattern[i+1][0],y2+pattern[i+1][1]
x4,y4 = x3+pattern[i+2][0],y3+pattern[i+2][1]
print(x3,y3,x4,y4)

Measured memory_bytes: 3064
n=int(input())
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
ans=1
cnt=[]
for j in range(1,n+1):
    d=list((prime_decomposition(j)))
    for i in range(len(d)):
        cnt.append(d[i])
cnt.sort()
c=[]
#print(cnt)
for i in range(len(cnt)):
    if i==0:
        a=cnt[i]
        ans+=1
        continue
    if a!=cnt[i]:
        c.append(ans)
        ans=2
        a=cnt[i]
    else:
        ans+=1
c.append(ans)
aa=1
for i in range(len(c)):
    aa*=c[i]
    aa%=10**9+7
print(aa)

Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	unsigned long int a, b, c;
	unsigned long long int num = 0, d = 1;
	
	vector<unsigned long int> v;
	scanf("%ld", &a);

	for (int i = 0; i < a; i++) {
		scanf("%ld", &b);
		v.push_back(b);
	}

	std::sort(v.begin(), v.end(), std::greater<int>());

	num = v[0];

	for (int i = 1; i < a; i++) {
		if (d == a - 1) {
			cout << num;
			return 0;
		}
		num += v[i];
		d++;

		if (d == a - 1) {
			cout << num;
			return 0;
		}
		num += v[i];
		d++;
	}

	return 0;
}

Measured memory_bytes: 5360
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long ll;
#define int long long
#define umap unordered_map
#define uset unordered_set
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000000000000;

struct UnionFind {
	vector<int> data;
 	UnionFind(int size):data(size, -1) {}
	bool unite(int x,int y){
		x=root(x);
		y=root(y);
 	   if(x!=y){
			if (data[y]<data[x]){
				swap(x, y);
			}
			data[x]+=data[y];
			data[y]=x;
		}
		return x!=y;
	}
	bool same(int x, int y){
		return root(x)==root(y);
	}
	int root(int x){
		return data[x]<0? x:data[x]=root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};



int N,M;
int A[100010],B[100010];

int nCr(int n, int r) {
	if(n==0)return 1;
	if(r*2>n)r=n-r;
	int dividend=1;
	int divisor=1;
	for (int i=1;i<=r;i++){
		dividend*=(n-i+1);
		divisor*=i;
	}
	return dividend/divisor;
}

signed main(){
	cin>>N>>M;
	vector<int> v;
	UnionFind UF(N);
	int sum=0;
	REP(i,M){
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
	}
	v.push_back(nCr(N,2));
	for(int i=M-1;1<=i;i--){
		if(UF.same(A[i],B[i])!=true){
			int az=UF.size(A[i]);
			int bz=UF.size(B[i]);
			if(az!=1){
				sum-=nCr(az,2);
			}
			if(bz!=1){
				sum-=nCr(bz,2);
			}
			UF.unite(A[i],B[i]);
			az=UF.size(A[i]);
			sum+=nCr(az,2);
		}
		v.push_back(nCr(N,2)-sum);
	}
	reverse(v.begin(),v.end());
	REP(i,v.size()){
		cout<<v[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 4596
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

  int n; cin >> n;
  vector<string> s(n);
  vector<vector<int> > bucket(n, vector<int>(26));
  rep(i, n) {
    cin >> s[i];
    rep(j, s[i].size()) {
      bucket[i][s[i][j]-'a']++;
    }
  }

  int minCnt[26] = {};
  rep(i, 26) minCnt[i] = 1e9;
  rep(i, n) rep(j, 26) {
    minCnt[j] = min(minCnt[j], bucket[i][j]);
  }

  string ans = "";
  rep(i, 26) {
    while(minCnt[i]--) ans += (char)(i+'a');
  }

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


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

using namespace std;

int A[200010], B[200010];

int main()
{
	int n;
	scanf("%d", &n);
	int w = 1, t = n;
	for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
	for(int i = n, b = 0; i >= 1; i--, b ^= 1)
		if(!b) B[w++] = A[i]; else B[t--] = A[i];
	for(int i = 1; i <= n; i++) printf("%d ", B[i]);//rintf("%d ", A[t--]); else printf("%d ", A[w++]);
	return putchar('\n'), 0;
}

Measured memory_bytes: 3712
#define _GLIBCXX_DEBUG //GCC環境での[]デバッグ
#include <bits/stdc++.h> //全ての標準ライブラリ
#define rep(i,n) for(int i = 0;i < n;i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
using namespace std;
using ll = long long;
int sumVector (const std::vector<int>& v){ //int配列計算
    int sum = 0;
    rep(i, v.size()) sum += v.at(i);
    return sum; 
}
int gcd(int i, int j){
return (i % j)? gcd(j, i % j): j; 
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, temp,sum = 0;
    cin >> n;
    n++;
    for(int i = 1;i < n;i++){
        for(int j = 1; j < n;j++){
            for(int k = 1; k < n; k++){
             //   cout << i << j << k << endl;
                temp = gcd(i,j);
                sum += gcd(temp,k);
            }
        }
    }
    cout << sum;
}

Measured memory_bytes: 3652
// H - Grid 1
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define MOD 1000000007

int main(){
	int H,W; cin>>H>>W;
	vector<string> A(H);
	for(int i=0; i<H; i++) cin>>A[i];
	vi dp(W+1);
	dp[W-1] = 1;
	for(int h=H-1; h>=0; h--) for(int w=W-1; w>=0; w--) dp[w] = A[h][w]=='.'? (dp[w] + dp[w+1]) % MOD: 0;
	cout<< dp[0] <<endl;
}

Measured memory_bytes: 1280