akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def solve(X: int):
    while True:
        if is_prime(X):
            ret = X
            break
        X += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
ll LCM(ll a,ll b){return (a*b)/GCD(a,b);}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	int n;
	cin >> n;
	int w[n];
	int a[n] = {};
	REP(i, n){
		cin >> w[i];
		if (i == 0){
			a[0] = w[0];
		}
		else {
			a[i] = a[i-1] + w[i];
		}
	}

	int ans = INF;

	REP(i, n){
		ans = min(abs(a[n-1]-(a[i]*2)) , ans);
	}

	cout << ans << endl;



}


Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;
public class Main {
	final static PrintStream so = System.out;
	final static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int[] a = sc.next().chars().map(i -> i-'0').toArray();
		String[] ops = new String[3];
		
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					ops[0] = i == 0 ? "+" : "-";
					ops[1] = j == 0 ? "+" : "-";
					ops[2] = k == 0 ? "+" : "-";
					if (ev(a, ops) == 7) {
						so.println(a[0] + ops[0] + a[1] + ops[1]+ a[2] + ops[2] + a[3] + "=7");
						return;
					}
				}
			}
		}
	}
	
	static int ev(int[] a, String[] ops) {
		int ans = a[0];
		for (int i = 0; i < ops.length; i++) {
			if (ops[i].equals("+")) ans += a[i+1];
			else ans -= a[i+1];
		}
		return ans;
	}
}


Measured memory_bytes: 28884
#include <iostream>
#include <cmath>
using namespace std;
int a[100][100],b[100][100];
bool dp[81][81][15000];
int main(){
	int i,j,k,h,w;
	cin >> h >> w;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin >> a[i][j];
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin >>b[i][j];
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			for(k=0;k<15000;k++){
				dp[i][j][k] = false;
			}
		}
	}
	dp[0][0][abs(a[0][0] - b[0][0])] = true;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			for(k=0;k<15000;k++){
				if(!dp[i][j][k]) continue;
				dp[i + 1][j][abs(k + a[i + 1][j] - b[i + 1][j])] = true;
				dp[i + 1][j][abs(k - a[i + 1][j] + b[i + 1][j])] = true;
				dp[i][j + 1][abs(k + a[i][j + 1] - b[i][j + 1])] = true;
				dp[i][j + 1][abs(k - a[i][j + 1] + b[i][j + 1])] = true;
			}
		}
	}
	for(i=0;i<15000;i++){
		if(dp[h - 1][w - 1][i]){
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 96256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

int main(){
    ll N;
    cin >> N; 
    ll digits = 0,rest;
    bool all9 = true;

    while(true){
        digits++;
        rest = N % 10;
        N /= 10;
        if(N <= 0) break;
        if(rest != 9) all9 = false;
    }
    
    if(all9 && digits != 1)
        cout << rest + (digits - 1) * 9 << "\n";
    else if(1 == digits)
        cout << rest << "\n";
    else
        cout << rest - 1 + (digits - 1) * 9 << "\n";
    return 0;
}


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

int main(void){
    int n;
    string s;
    
    cin >> n >> s;
    
    for(int i = 0; i < s.size(); i++){
        s[i] = (s[i] - 'A' + n) % 26 + 'A';
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	ans := 1
	for i := 0; i < 3; i++ {
		ans *= n
	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}


Measured memory_bytes: 640
//                                               KEEP GRINDING
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>   new_data_set;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define int long long
#define ld long double
#define MOD 1000000007
#define mod 998244353
#define precise(i) fixed << setprecision(10) << i
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n"<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define all(a) a.begin(),a.end()
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define mx(a) *max_element(a)
#define mn(a) *min_element(a) 
#define LB lower_bound  //THIS GIVES THE ITR TO THE ELEMENT IN RANGE [SI,EI) THAT IS >= OUR VALUE 
#define UB upper_bound  //THIS GIVES THE ITR TO THE ELEMENT IN RANGE [SI,EI) THAT IS > OUR VALUE 

#define fr first
#define sc second

#define MAXN 500000
#define INF 9223372036854775807
int N,K;
vector<int> help(vector<int> A){
   
	vector <int> B(N,0); 
	for(int i=0;i<N;i++){ 
	    int l=max((int)0,i-A[i]);
		int r=min(N-1,i+A[i]);
		B[l]++;
		if(r+1<N) 
		    B[r+1]--; 
	}
	for(int i=1;i<N;i++) B[i]+=B[i-1];
	return B; 
}
signed main(){
    fastio
    cin >> N >> K;
    vector< int > a(N);
    f(i,0,N)
    	cin >> a[i];
	
	K=min(K,(int)42);
	for(int i=1;i<=K;i++){
		a=help(a);
	}
	show(a);
}

Measured memory_bytes: 7952
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

use std::cmp::min;

fn main() {
    let a: Vec<char> = read::<String>().chars().collect();
    let b: Vec<char> = read::<String>().chars().collect();
    let c: Vec<char> = read::<String>().chars().collect();

    if a[a.len() - 1] == b[0] && b[b.len() - 1] == c[0] {
        println!("YES")
    } else {
        println!("NO")
    }
}


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

typedef long long int lint;


int main(){
    int n;
    cin >> n;
    int arr[n];
    lint sonuc = 0;
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            sonuc+= arr[i]*arr[j];
        }
    }
    cout << sonuc;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int lli;
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define eb emplace_back
/*unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);
*/
vector<lli> edges[200002];
lli visited[200002],power[200002];
void dfs(lli i)
{
    visited[i]=1;
    for(auto j: edges[i])
    {
        if(visited[j]==0)
        {
            power[j]+=power[i];
            dfs(j);
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    lli n,t,i,j,a,b,q;
    cin>>n>>q;
    for(i=0;i<n-1;i++)
    {
        cin>>a>>b;
        edges[a].eb(b);
      edges[b].eb(a);
    }
    while(q--)
    {
        cin>>a>>b;
        power[a]+=b;
    }
    dfs(1);
    for(i=1;i<=n;i++)
        cout<<power[i]<<" ";
    return 0;
}


Measured memory_bytes: 22784
fun main(args: Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toDouble() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    val sum = a.reduce { acc, i -> acc + i }
    if (a.sortedDescending()[m.toInt()-1] >= sum / (4 * m)) println("Yes") else println("No")
}

Measured memory_bytes: 41016
function main(arg) {
	arg = arg.trim().split('\n');
  	var n = Number(arg.shift());
  	var a = arg[0].split(' ').map(str => parseInt(str, 10)),
        b = arg[1].split(' ').map(str => parseInt(str, 10)),
        c = arg[2].split(' ').map(str => parseInt(str, 10));
  	var out = 0;

  	for (var i = 0; i < n; i++){
      	out += b[a[i]-1];
    	if (a[i] + 1 == a[i+1]){
        	out += c[a[i]-1];
        }
    }
  	console.log(out)
  	
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;

int main() {
  int N, K;
  cin >> N >> K;

  int res = K * pow(K - 1, N - 1);
  cout << res << endl;
}

Measured memory_bytes: 256
from collections import deque

N, M = list(map(int, input().split()))

adjacency_list = [[] for i in range(N)]
for i in range(M):
    tmp = list(map(int, input().split()))
    adjacency_list[tmp[0] - 1].append(tmp[1] - 1)
    adjacency_list[tmp[1] - 1].append(tmp[0] - 1)
con_component = 0
# 接続確認
# print(adjacency_list)
visited_set = set(range(N))
queue = deque()
while visited_set:
    con_component += 1
    queue.append(visited_set.pop())
    while len(queue) != 0:
        ind = queue.popleft()
        # print("start queue", ind)
        for adjacency in adjacency_list[ind]:
            # print("aa",adjacency)
            if adjacency in visited_set:
                visited_set.remove(adjacency)
                queue.append(adjacency)
print(con_component - 1)


Measured memory_bytes: 94504
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
int main(){
	int a, b;
	cin >> a >> b;
	if (a%b == 0) {
		cout << 0 << endl;
	}
	else{
		cout << 1 << endl;
    }
	return 0;
}

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

int main(){
    ll l, r;
    cin >> l >> r;
    ll tmp = r-l;
    ll ans = 30000;
    if(tmp >= 2018) cout << 0 << endl;
    else{
        for(ll i = l; i < r; i++){
            for(ll j = i + 1; j <= r; j++){
                ll res = (i*j)%2019;
                ans = min(res, ans);
            }
        }
        cout << ans << endl;
    }
}


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

void solve() {
	int n, y;
	cin >> n >> y;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			int rem = y - i * 10000 - j * 5000;
			if (rem / 1000 == n - i - j && rem / 1000 >= 0) {
				cout << i << ' ' << j << ' ' << rem / 1000;
				return;
			}
		}
	}
	cout << -1 << ' ' << -1 << ' ' << -1;
}

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

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

int main() {
	int a,b,c,k;
  	cin>>a>>b>>c>>k;
  
  	ll max=0;
  
  	for(int i=0;i<a;i++){
        if(k>0){
         k--;
         max++;

        }      
      else{
        break;
      }
    }
   
    for(int j=0;j<b;j++){
	   if(k>0){
         
          k--;
         }
       else{
        break;
       }
    
    }
  
 
      
     for(int m=0;m<c;m++){
         if(k>0){
         k--;
        max--;
        }
        else{
          break;
}
   
     }
       
        cout<<max<<endl;
  		
      
    }
    
  	



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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    vector<int> mx(n);
    rep(i, n) {
        cin >> h[i];
        mx[i] = 0;
    }
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        mx[a] = max(mx[a], h[b]);
        mx[b] = max(mx[b], h[a]);
    }
    int ans = 0;
    rep(i, n) {
        if (h[i] > mx[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4032
//https://atcoder.jp/contests/abc154/tasks/abc154_e
//E - Almost Everywhere Zero
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
    string N; cin>>N;
    ll K; cin>>K;    
    //vector<vector<vector<ll>>> dp_b(vector(N.size()+1,vector(2,vector<ll>(5))));
    vector<vector<vector<ll>>> dp_b(N.size()+1, vector<vector<ll>>(2, vector<ll>(5)));
    dp_b[0][0][0]=1;
    for(ll k=0;k<N.size();++k){ //桁
        ll digit = N[k]-'0';
        for(ll f=0;f<4;++f){ //0でない数字の数0,1,2,3,4以上
            for(ll d=0;d<=9;++d){ //未満フラグ1
                ll not0num = f + (d!=0);
                dp_b[k+1][1][not0num] += dp_b[k][1][f];
            }
            for(ll d=0;d<=digit;++d){ //未満フラグ0
                ll not0num = f + (d!=0);
                dp_b[k+1][(d<digit)][not0num] += dp_b[k][0][f]; //未満フラグ0は桁数があっているとき
            }
        }
    }
    ll bnum= dp_b[N.size()][0][K]+dp_b[N.size()][1][K];
    cout<<bnum<<endl;
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>

template<class T>
void dwrite(T o){
	std::cout << o << std::endl;
}

std::string itos(int i){
  std::stringstream ss;
  ss<<i;
  
  return ss.str();
}

std::string Xtoi(std::string s,int i){
  std::string t = s;
  int find;
  while(find = t.find("X"),find != std::string::npos){
    t.replace(find,1,itos(i));
  }

  return t;
}

//multiple-recision computation
std::string mpc(std::string a, std::string b){
	int n[50] = {0};
	std::reverse(a.begin(),a.end());
	std::reverse(b.begin(),b.end());

	for(int i=0;i<a.size();i++){
		n[i] = a[i] - '0';
	}
	for(int j=0;j<b.size();j++){
		n[j] += b[j] - '0';
	}
	for(int k=0;k<50;k++){
		if(n[k] >= 10){
			n[k] -= 10;
			n[k+1]++;
		}
	}
	int digit = 0;
	for(int l=49;l>=0;l--){
		if(n[l]){digit = l;break;}
	}
	
	std::string res = "";
	for(int i=0;i<=digit;i++){
		res = itos(n[i]) + res;
	}

	return res;
}

int main(){
  std::string s;

  while(std::cin>>s,!std::cin.eof()){
    int p = s.find("+"),e = s.find("=");
    std::string a = s.substr(0,p),b = s.substr(p+1,e-p-1),c = s.substr(e+1,s.size()-e-1);

    int x0 = (!(a.find("X")) && a.size() > 1) || (!(b.find("X")) && b.size() > 1) || (!(c.find("X")) && c.size() > 1);

    int res = -1;
    for(int i=x0;i<=9;i++){
			std::string t_a = Xtoi(a,i), 
				t_b = Xtoi(b,i), 
				t_c = Xtoi(c,i);
      if(!t_c.compare(mpc(t_a,t_b))){res = i;break;}
    }

    if(res>=0)std::cout<<res<<std::endl;
    else{std::cout<<"NA"<<std::endl;}
  }
}

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

int main()
{
    int A;
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        cin >> A;
        sum += A;
    }
    if (sum >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <iostream>
 
using namespace std;
 
int main() {
  int K,N;
  int A[200000];

  cin >> K >> N;
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  // 基本は配列の最後を抜いたやつ
  // ただし、配列のから2番目が抜群に長いとき、要検討

  int disMax = K - A[N-1]+A[0];
  for(int i=1;i<N;i++){
    if ( A[i] - A[i-1] > disMax ){
      disMax = A[i] - A[i-1];
    }
  }
  cout << K - disMax<< endl;
  

  /*
  cout << K << N << endl;
  for(int i=0;i<N;i++){
    cout << A[i];
  }
  cout << endl;
  */
  
}

Measured memory_bytes: 1024
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

ll modpow(ll a, ll p, ll m){
    ll ret = 1;
    while(p){
	if(p%2) ret = ret * a  % m;
	a = a * a % m;
	p >>= 1;
    }
    return ret;
}

int main(){
    int n;
    scanf("%d", &n);
    char s[n+1];
    scanf("%s", s);

    ll cnt = 0;
    REP(i, 0, n) cnt += (s[i]=='1');

    ll X = 0, incX = 0, decX = 0;
    ll r = 1, incr = 1, decr = 1;
    for(int i=n-1; i>=0; i--){
	if(s[i]=='1'){
	    X = (X + r) % cnt;
	    incX = (incX + incr) % (cnt+1);
	    if(cnt>1) decX = (decX + decr) % (cnt-1);
	}
	r = r * 2 % cnt;
	incr = incr * 2 % (cnt+1);
	if(cnt>1) decr = decr * 2 % (cnt-1);
    }

    REP(i, 0, n){
	ll x;
	if(s[i]=='1'){
	    if(cnt!=1){ 
	    	x = decX;
	    	x -= modpow(2, n-1-i, cnt-1);
	    	x = (x+cnt-1) % (cnt-1);
	    }else{
		puts("0");
		continue;
	    }
	} else {
	    x = incX;
	    x += modpow(2, n-1-i, cnt+1);
	    x = (x+cnt+1) % (cnt+1);
	}
	int ans = 1;
	while(x){
	    x %= __builtin_popcount(x);
	    ans++;
	}
	printf("%d\n", ans);
    }
    return 0;
}



Measured memory_bytes: 3964
#include <iostream>

#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::vector;

static int
solve(int N, vector<int> const &X)
{
  int min_cost = 100 * 100 * 100;
  for (int P = 0; P <= 100; P++)
  {
    int cost = 0;
    for (int n = 0; n < N; n++)
    {
      int d = (X[n] - P);
      cost += d * d;
    }
    if (cost < min_cost)
    {
      min_cost = cost;
    }
  }
  return min_cost;
}

int
main()
{
  int N;
  cin >> N;
  vector<int> X(N);
  for (int n = 0; n < N; n++)
  {
    cin >> X[n];
  }
  cout << solve(N, X) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    ll N,M,K;
    cin >> N >> M >> K;
    graph G(N);
    graph B(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        B[a].push_back(b);
        B[b].push_back(a);
    }
    int group[N];
    ll currentG = 0;
    queue<ll> q = queue<ll>();
    for (int i = 0; i < N; ++i) {
        group[i] = -1;
    }
    for(int i = 0; i < N; i++){
        if(group[i] != -1){
            continue;
        }
        group[i] = currentG;
        q = queue<ll>();
        q.push(i);
        while(!q.empty()){
            ll current = q.front();q.pop();
            for (int j = 0; j < G[current].size(); ++j) {
                ll next = G[current][j];
                if(group[next] != -1){
                    continue;
                }
                group[next] = group[current];
                q.push(next);
            }
        }
        currentG++;
    }
    ll gCount[currentG+1ll];
    for (int i = 0; i < currentG + 1; ++i) {
        gCount[i] = 0;
    }
    for (int i = 0; i < N; ++i) {
        gCount[group[i]]++;
    }

    for (int i = 0; i < N; ++i) {
        ll count = gCount[group[i]];
        for (int j = 0; j < G[i].size(); ++j) {
            ll fam = G[i][j];
            if(group[i] == group[fam]){
                count--;
            }
        }
        for (int j = 0; j < B[i].size(); ++j) {
            ll enemy = B[i][j];
            if(group[i] == group[enemy]){
                count--;
            }
        }
        cout << count-1 << " ";
    }
    cout << endl;

}


Measured memory_bytes: 14196
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    int n, m;
    cin >> n;
    vector<int> s(n), l(n), p(n);
    rep(i, n) cin >> s[i] >> l[i] >> p[i];
    cin >> m;
    vector<int> w(m);
    rep(i, m) cin >> w[i];
    vector<int> dp(394, -1);
    dp[0] = 0;
    rep(i, n) {
        rep(j, 394) {
            for (int k = j+s[i]; k<=j+l[i]; ++k) {
                if (k <= 393) chmax(dp[k], dp[j] + p[i]);
            }
        }
    }
    vector<int> ans(m);
    rep(i, m) {
        ans[i] = dp[w[i]];
        if (ans[i] == -1) {
            cout << -1 << endl;
            return 0;
        }
    }
    rep(i, m) cout << ans[i] << endl;
}


Measured memory_bytes: 3116
#include<iostream>
using namespace std;
int main(){
    int a,b,x;
    char op;
    cin >> a >> op >> b;
    while(op!='?'){
        if (op=='+'){x=a+b;}
        else if (op=='-'){x=a-b;}
        else if (op=='*'){x=a*b;}
        else if (op=='/'){x=a/b;}
        cout << x << endl;
        cin >> a >> op >> b;
    }return 0;
}


Measured memory_bytes: 3084
import java.util.Scanner;

public class  Main{

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();
		int a=sc.nextInt();
		int b=sc.nextInt();
		int ans=(x-a)%b;
		System.out.println(ans);

	}

}


Measured memory_bytes: 20948
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define vvll vector<vll>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define pii pair<int, int>
#define vpli vector<pair<long long, int>>
#define deb(x) cout << "deb " << #x << " " << x << endl
#define all(x) x.begin(), x.end()
#define endl "\n"
int cycle_len;

void dfs(int s,vi& vis,vvi &adj,int& tot)
{
    tot++;
    for(int x : adj[s])
    {
        if(!vis[x])
        {
            vis[x] = vis[s]+1;
            dfs(x,vis,adj,tot);
        }
        else
        {
            cycle_len = vis[s] - vis[x]+1;
            return;
        }
        
    }
}
int dfs2(int s,vvi& adj,int k)
{
    if(k==0) return s+1;
    for(int x : adj[s])
    {
        return dfs2(x,adj,k-1);
    }
}
void solve()
{
    int n;
    ll k;
    cin>>n>>k;
    vvi adj(n);
    int u;
    for(int i=0;i<n;i++)
    {
        cin>>u;
        u--;
        adj[i].pb(u);
    }
    vi vis(n,0);
    vis[0] =1;
    int tot = 0;
    dfs(0,vis,adj,tot);
    int non_cyc = tot-cycle_len; 
    if(k>tot)
    {
        k -= non_cyc;
        k = k%cycle_len;
        k += non_cyc;
    }
    cout<<dfs2(0,adj,k); 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //pre();
    int t = 1;
    //cin >> t;
    //cout<<__gcd(-5,0)<<endl;
    while (t--)
        solve();
    return 0;
}


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

int main(void)
{
    int i;
    char s[100];
    
    scanf("%s", s);
    
    for (i = 1; i <= strlen(s); i ++) {
        if ((i % 2 == 0 && s[i - 1] == 'R')
            || (i % 2 == 1 && s[i - 1] == 'L')) {
            printf("No\n");
            return 0;
        }
    }

    printf("Yes\n");
    
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RREP(i,x) for(int i=(x)-1;i>=0;i--)
#define RFOR(i,c) for(auto i=(c).rbegin();i!=(c).rend();++i)
#define ALL(container) container.begin(), container.end()
#define SZ(container) ((int)container.size())

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

vi eratosthenes_sieve(int n){
	vi res(n+1);
	if(n<2) return res;
	res[2]=1;
	for(int i=3;i<=n;i+=2){
		if(i*i<=n && !res[i]) for(int j=i+i+i;j<=n;j+=i+i) res[j]=1;
		res[i]=!res[i];
	}
	return res;
}
vi prime_list(const vi& isprime){
	vi res;if(isprime.size()<=2)return res;
	res.push_back(2);
	for(unsigned int i=3;i<isprime.size();i+=2)
		if(isprime[i])res.push_back(i);
	return res;
}
vi prime_list(int n){
	return prime_list(eratosthenes_sieve(n));
}

int n, p;
main(){
	vi pl = prime_list(200000);
	while(cin >> n >> p, n >= 0){
		auto it = upper_bound(ALL(pl), n);
		vi l;
		REP(i, p)REP(j, i+1) l.push_back(*(it+i) + *(it+j));
		sort(ALL(l));
		cout << l[p-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1788
#include <stdio.h>

#define ANUM(x) (sizeof(x) / sizeof((x)[0]))

typedef enum {
    FALSE = 0,
    TRUE = 1
} BOOL;

int main(void) {
    int a[3];
    
    scanf("%d %d %d", &a[0], &a[1], &a[2]);
    
    for (int i = 0; i < ANUM(a); ++i) {
        for (int j = i + 1; j < ANUM(a); ++j) {
            if (a[i] > a[j]) {
                int x = a[i];
                a[i] = a[j];
                a[j] = x;
            }
        }
    }

    printf("%d %d %d\n", a[0], a[1], a[2]);

    return 0;
}



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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 2e5 + 5;

int arr[maxr];
int32_t main()
{
	GO;
	int n;
	cin >> n;
	int x = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		x ^= arr[i];
	}
	for (int i = 0; i < n; i++) {
		cout << (arr[i] ^ x) << " ";
	}
	return 0;
}

//!

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

int main(){
int n;
  cin >> n;
if(n>1){  
int x[n];
  for(int i=0;i<n;i++)cin>>x[i];
sort(x,x+n);  
int num[1000000]={0};
  for(int i=0;i<n;i++){
  num[x[i]-1]++;
  num[x[i]]++;
  num[x[i]+1]++;
 }
  
int max=-1;

for(int i=x[0];i<x[n-1]+1;i++){
  int s=num[i];
  if(s>max)max=s;
} 
cout << max << endl;  
}
else{
  cout << 1 << endl; 
}
  
}


Measured memory_bytes: 7892
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
        int n;
        scanf("%d", &n);
        ll a[1+n];
        REP(i, 1, 1+n) scanf("%ld", &a[i]);
        a[0] = 0;

        ll ans = 0;
        REP(i, 1, 1+n){
                ll diff = std::max(0l, a[i-1]-a[i]);
                ans += diff;
                a[i] += diff;
        }
        printf("%ld\n", ans);
        return 0;
}

Measured memory_bytes: 5320
use proconio::marker::Usize1;
use superslice::Ext;
static INF: i32 = std::i32::MAX;
fn main() {
    proconio::input! {
        n: usize,
        a: [i32;n],
        uv: [(Usize1,Usize1);n-1],
    }
    let mut g = vec![vec![];n];
    for (u,v) in uv {
        g[u].push(v);
        g[v].push(u);
    }
    let mut dp = vec![INF;n];
    let mut r = vec![0;n];
    f(0, &mut dp, &mut r, &a, &g);
    for r in r {
        println!("{}",r);
    }
}
fn f(v: usize, dp: &mut Vec<i32>, r: &mut Vec<usize>, a: &Vec<i32>, g: &Vec<Vec<usize>>) {
    let x = a[v];
    let k = dp.lower_bound(&x);
    let b = dp[k];
    dp[k]=x;
    r[v]=dp.lower_bound(&INF);
    for &u in &g[v] { if r[u]==0 {
        f(u, dp, r, a, g);
    }}
    dp[k]=b;
}

Measured memory_bytes: 33456
import java.util.*;
import static java.lang.System.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(in);
		int N = sc.nextInt();
		
		int p[] = new int[N];
		int org[] = new int[N];
		for(int i=0;i<N;i++) {
			p[i] = sc.nextInt();
			org[i] = p[i];
		}
		Arrays.sort(p);
		
		int check = 0;
		for(int i=0;i<N;i++) {
			if(p[i]!=org[i]) {
				if(check==2) {
					out.println("NO");
					return;
				}
				check++;
			}
		}
		out.println("YES");
		sc.close();
	}
}

Measured memory_bytes: 23764
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,A = map(int,input().split())

    if H % A == 0:
        res = H // A
    else:
        res = H // A + 1

    print(res)



main()


Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Linq;

namespace _0030
{
    class Program
    {
        static int[] head;
        static List<long>[] que;

        static void Inqueue(int num, long key)
        {
            if(head[num] == -1)
            {
                head[num] = 0;
            }
            que[num].Add(key);
        }

        static long Front(int num)
        {        
            return que[num][head[num]];
        }

        static void Dequeue(int num)
        {
            if(head[num] > que[num].Count - 1 || head[num] == -1)
            {
                return;
            }
            head[num]++;
        }


        static void Initial(int k)
        {
            for(int i = 0; i < k; i++)
            {
                head[i] = -1;
                que[i] = new List<long>();
            }
        }

        static void Main(string[] args)
        {

            string[] str = Console.ReadLine().Split(' ');

            int n = int.Parse(str[0]);
            int q = int.Parse(str[1]);

            que = new List<long>[q];

            head = new int[n];

            Initial(n);
            
            for(int i = 0; i < q; i++)
            {
                string[] input = Console.ReadLine().Split(' ');

                int order = int.Parse(input[0]);
                int num = int.Parse(input[1]);

                if(order == 0)
                {
                    long key = long.Parse(input[2]);
                    Inqueue(num, key);
                }
                else if(order == 1)
                {
                    if (head[num] > que[num].Count - 1 || head[num] == -1)
                    {
                        continue;
                    }
                    Console.WriteLine(Front(num));
                }
                else
                {
                    Dequeue(num);
                }
            }

        }
    }
}


Measured memory_bytes: 23256
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int N;
int A[101];
int B[101];
int main() {
	cin>>N;

	int C[101]={};
	int D[101]={};
	for(int i=1;i<N+1;i++){
		cin>>A[i];
		C[i]=C[i-1]+A[i];
	}
	for(int i=1;i<N+1;i++){
		cin>>B[i];
		D[i]=D[i-1]+B[i];
	}

	int R=0;
	for(int i=1;i<N+1;i++){
		R=max(R,C[i]+D[N]-D[i-1]);
	}

	cout<<R<<endl;

 	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  if(b-a == c-b){
    cout << "YES" << endl;
    return 0;
  }else{
    cout << "NO" << endl;
    return 0;
  }
}

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

typedef long long ll;

void mult(ll m, const ll x[3][3], const ll y[3][3], ll z[3][3]) {
	for(int i=0;i<3;i++) for(int j=0;j<3;j++) {
		z[i][j] = 0;
		for(int k=0;k<3;k++) {
			z[i][j] += x[i][k] * y[k][j];
		}
		z[i][j] %= m;
	}
}

int main() {
	ll l, a, b, m;
	cin >> l >> a >> b >> m;
	ll ans = 0;
	for(ll r=10;l>0;r*=10) {
		if(r <= a) continue;
		ll n = (r-a-1) / b + 1;
		if(n > l) n = l;
		ll mat[3][3] = {
			{r % m, 0, 0},
			{1, 1, 0},
			{0, b % m, 1}
		};
		ll p[3][3] = {
			{1, 0, 0},
			{0, 1, 0},
			{0, 0, 1}
		};
		for(int s=63;s>=0;s--) {
			ll tmp[3][3];
			mult(m, p, p, tmp);
			if((n >> s) & 1) {
				mult(m, tmp, mat, p);
			} else {
				for(int i=0;i<3;i++) for(int j=0;j<3;j++) p[i][j] = tmp[i][j];
			}
		}
		ll v[3] = {ans, a % m, 1};
		ans = 0;
		for(int i=0;i<3;i++) {
			ans += v[i] * p[i][0];
		}
		ans %= m;
		l -= n;
		a += b * n;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
s=[]
s.append("."*(w+2))

for i in range(h):
    s.append("."+input()+".")
    
s.append("."*(w+2))

for i in range(1,h+1):
    for j in range(1,w+1):
        #print(i,j)
        if s[i][j]=="#":
            if s[i][j+1]=="#" or s[i][j-1]=="#" or s[i+1][j]=="#" or s[i-1][j]=="#":
                pass
            else:
                print("No")
                exit()
        

print("Yes")

Measured memory_bytes: 3064
(* O(n^2) *)
let solve r g b n =
  let rec find_g acc g0 m =
    if g0 * g > m then
      acc
    else
      find_g 
        (acc + if (m - g0 * g) mod b = 0 then 1 else 0)
        (g0 + 1)
        m in
  let rec count acc r0 =
    if r0 * r > n then
      acc
    else
      count (find_g acc 0 (n - r0 * r)) (r0 + 1)
  in
    count 0 0

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

let _ =
  match read_ints () with
  | [r; g; b; n] -> solve r g b n |> string_of_int |> print_endline
  | _ -> assert false

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cstdlib> 
using namespace std;

int N;

int main()
{
    cin >> N;
    bool flag = true;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        if (temp % 2 == 0 && temp % 3 != 0 && temp % 5 != 0)
        {
            flag = false;
            break;
        }
    }
    cout << (flag ? "APPROVED" : "DENIED") << endl;
    // system("pause");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll x,n;
  cin >> x >> n;
  set<ll> s;
  rep(i,n) {
    ll z;
    R z;
    s.in(z);
  }
  int M=MAX,y;
  REP(i,-5,111) {
    if(!s.count(i)&&abs(x-i)<M) {
      M=abs(x-i);
      y=i;
    }
  }
  pr(y);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3664
# coding: utf-8
# Your code here!
from math import gcd
K = int(input())+1
Sum = 0
for i in range(1,K):
    for j in range(1,K):
        d = gcd(i,j)
        for k in range(1,K):
            Sum+=gcd(d,k)

print(Sum)

Measured memory_bytes: 9092
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>
#include <list>
#include <iomanip>
#include <cctype>
#include<chrono>
#include<random>

#define for0(i, N)    for (long long i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (long long i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (long long i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (long long i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (long long i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (long long i = (x), a = 0; a < (N);    \
                              i = (i + 1) % (N), ++a)
#define int long long

long double constexpr pi = 3.141592653589793;

template<class T>
constexpr T sigma1(T i, T n){
    return (n - i + 1) * (i + n) / 2;
}

template<class T>
constexpr T sigma2(T i, T n){
    return (i == 1 ? n * (n + 1) * (2 * n + 1) / 6 :
            sigma2(1, n) - sigma2(1, i - 1));
}

template<class T>
constexpr T sigma3(T i, T n){
    if (i == 1) {
        auto temp = sigma1(i, n);
        return temp * temp;
    }
    return sigma2(1, n) - sigma2(1, i - 1);
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

long long constexpr inf = std::numeric_limits<long long>::max();

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<vector<ll>> vvll;


signed main(void){
    cin.tie(0); ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);
    ll n;
    cin >> n;

    vll a(n + 1);

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

    vll p(n + 1, 0), q(n + 1, 0);

    for1n(i, n){
        p[i] = i + a[i];
        q[i] = i - a[i];
    }


    unordered_map<ll, pair<ll, ll>> m;

    for1n(i, n){
        ++m[p[i]].first;
        ++m[q[i]].second;
    }


    ll result = 0;
    for(auto &x : m){
        result += x.second.first * x.second.second;
    }

    cout << result;;

    return 0;
}


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

const int inf=1e9;
int dp[10000010][2];

int main(){
    string s; cin >> s;
    int N=s.size();
    dp[0][0]=0;
    dp[0][1]=1;
    for(int i=0;i<N;i++){
        int d=s[i]-'0';
        dp[i+1][0]=min(dp[i][0]+d,dp[i][1]+10-d);
        dp[i+1][1]=min(dp[i+1][0]+1,dp[i][1]+10-(d+1));
    }
    cout << dp[N][0] << endl;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

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

  string s, t;

  cin >> s >> t;
  vvl dp(t.size()+1, vl(s.size()+1, 0));

  FOR(j, 1, t.size()+1)FOR(i, 1, s.size()+1){
    if(t[j-1]==s[i-1]){
      dp[j][i] = dp[j-1][i-1]+1;
    }
    else{
      dp[j][i] = max(dp[j][i-1], dp[j-1][i]);
    }
  }

  ll j = t.size();
  ll i = s.size();

  string out= "";
  while(i > 0 && j > 0){
    if(t[j-1]==s[i-1]){
      out = s[i-1]+out;
      j--;
      i--;
    }
    else{
      if(dp[j-1][i] > dp[j][i-1]){
        j--;
      }
      else{
        i--;
      }
    }
  }

  cout << out << endl;

}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

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

    int N;
    cin >> N;
    vector<ll> a(N);
    for (int i = 0; i < N; i++)
        cin >> a[i];
    ll res = a[0] - 1, c = 2;
    for (int i = 1; i < N; i++)
    {
        if (a[i] == c)
        {
            c++;
            continue;
        }
        if (a[i] % c)
        {
            res += a[i] / c;
        }
        else
        {
            if (a[i] >= c + 1)
            {
                res += 1 + (a[i] - c - 1) / c;
            }
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 998244353;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd_calc(T a, T b){ if(b){ return gcd_calc(b, a % b); }else{ return a; }}
template<class T> T gcd(T a, T b){ if(a < b) swap(a, b); return gcd_calc(a, b); }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
inline int at(int x, int k){ return (x >> k) & 1; }
random_device rnd;

int N;

void output(int now, int chars, string ans){
    if(now == N){
        cout << ans << endl;
        return;
    }
    for(int i = 1; i <= chars + 1; i++){
        output(now + 1, max(i, chars), ans + char('a' + i - 1));
    }
}

int main(){
    cin >> N;
    output(0, 0, "");
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
using namespace std;
int main () {
    int cnt=0;
    string N, M, check[20]={"KIHBR", "AKIHBR", "KIHABR", "KIHBAR", "KIHBRA", "AKIHABR", "AKIHBAR", "AKIHBRA", "KIHABAR", "KIHABRA", "KIHBARA", "AKIHABAR", "AKIHABRA", "AKIHBARA","KIHABARA", "AKIHABARA" };
    cin >> N;
    for (int i=0;i<16;i++){
        if (N==check[i])
            cnt++;
    }
    cnt ? cout << "YES" : cout << "NO";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
using namespace std;
typedef pair<int,int> P;//Pでpair<-,->を表す。
typedef long long LL; 
LL MOD=1000000007;

int main()
{ 
    int h,w,K;
    cin>>h>>w>>K;
    int ans=100000;
    int a[h][w];
    string s;
    for(int i=0;i<h;i++){
        cin>>s;
        for(int j=0;j<w;j++){
            if(s[j]=='1'){a[i][j]=1;}
            else{a[i][j]=0;}
        }
    }
    int b[h];
    int cnt[h];
    int mem[h];
    int pow[h+1];
    for(int i=0;i<h+1;i++){
        if(i==0){pow[i]=1;}
        else{pow[i]=pow[i-1]*2;}
    }
    for(int i=0;i<pow[h-1];i++){
        for(int j=0;j<h;j++){
            if(j==0){b[j]=0;}
            else{
                if((i/pow[j-1])%2==1){b[j]=b[j-1]+1;}
                else{b[j]=b[j-1];}
            }
        }
        /*for(int j=0;j<h;j++){cout<<b[j]<<' ';}
        cout<<endl;
        */
        int d=b[h-1]+1;
        for(int i=0;i<h;i++){
            cnt[i]=0;mem[i]=0;
        }
        int x=d-1;
        int flg=1;
        for(int j=0;j<w;j++){
            for(int k=0;k<h;k++){
                mem[k]=0;
            }
            for(int k=0;k<h;k++){
                if(a[k][j]==1){mem[b[k]]++;}
            }
            for(int k=0;k<d;k++){
                if(mem[k]>K){flg=0;}
                if(cnt[k]+mem[k]>K){
                    x++;
                    for(int l=0;l<d;l++){
                        cnt[l]=mem[l];
                    }
                    break;
                }
                else{cnt[k]=cnt[k]+mem[k];}
            }
            //cout<<x<<' ';
        }
        //cout<<x<<endl;
        if(ans>x&&flg==1){ans=x;}
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
	int n;
	int arr[10];
	memset(arr,0,sizeof(arr));
	scanf("%d",&n);
	int baseans=0;
	int lans=0;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		if(x<400) arr[0]+=1;
		else if(x>=400&&x<800) arr[1]+=1;
		else if(x>=800&&x<1200) arr[2]+=1;
		else if(x>=1200&&x<1600) arr[3]+=1;
		else if(x>=1600&&x<2000) arr[4]+=1;
		else if(x>=2000&&x<2400) arr[5]+=1;
		else if(x>=2400&&x<2800) arr[6]+=1;
		else if(x>=2800&&x<3200) arr[7]+=1;
		else if(x>=3200)lans+=1;
	}
	for(int i=0;i<8;i++) if(arr[i]>0) baseans+=1;
	lans+=baseans;
	if(baseans==0) baseans=1;
	cout << baseans << " " << lans << endl;
}

Measured memory_bytes: 256