akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<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()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let mut nums: Vec<Vec<usize>> = vec![vec![0; 10]; 10];
    for i in 1..=N {
        let first = i.to_string().chars().next().unwrap().to_digit(10).unwrap() as usize;
        let last = i.to_string().chars().last().unwrap().to_digit(10).unwrap() as usize;
        nums[first][last] += 1;
    }
    let mut ans = 0;
    for i in 0..=9 {
        for j in 0..=9 {
            ans += nums[i][j] * nums[j][i];
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2100
a,b,c,x,y=gets.split.map &:to_i
z=x<=y ? x: y
n=z*(a+b<c*2 ? a+b : c*2)+(x>y ? (a<=2*c ? a*(x-z) : 2*c*(x-z)) : (b<=2*c ? b*(y-z) : 2*c*(y-z)))
p n


Measured memory_bytes: 3836
#include <iostream>
#include <vector>
using namespace std;
void setDiff(const char dir, int* diff) {
    switch (dir) {
    case 'N':
        diff[0] = 0;
        diff[1] = 1;
        break;
    case 'E':
        diff[0] = 1;
        diff[1] = 0;
        break;
    case 'S':
        diff[0] = 0;
        diff[1] = -1;
        break;
    case 'W':
        diff[0] = -1;
        diff[1] = 0;
        break;
    default:
        diff[0] = 21;
        diff[1] = 21;
        break;
    }
}
int main()
{
    int n;
    const int W = 21;
    vector<string> result;
    int board[W][W];
    int diff[2] = {0};
    while (cin >> n && n) {
        fill(board[0], board[W], 0);
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            board[x][y] = 1;
        }
        int m, collection = 0;
        cin >> m;
        int cx = 10, cy = 10;
        for (int i = 0; i < m; ++i) {
            char dir;
            int dist;
            cin >> dir >> dist;
            setDiff(dir, diff);
            for (int j = 0; j < dist; ++j) {
                cx += diff[0];
                cy += diff[1];
                collection += board[cx][cy];
                board[cx][cy] = 0;
            }
        }
        result.push_back(collection == n ? "Yes" : "No");
    }
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
 
const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;
 
int n;
char s[N];
int main()
{
	scanf("%s", s);
	n = strlen(s);
	for(int i = 0; i < n; i++)
		if(s[i] == '?')
			s[i] = 'D';
	for(int i = 0; i < n; i++)
		printf("%c", s[i]);
}


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

bool usednumber[1000005];
bool ng[1000005];

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)  cin >> a[i];
    sort(a.begin(), a.end());
    a.emplace_back(a.back() + 1);
    
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(usednumber[a[i]] || ng[a[i]])    continue;
        usednumber[a[i]] = true;
        if(*lower_bound(a.begin() + i + 1, a.end(), a[i]) != a[i])  ++ans;
        for(int j = a[i] * 2; j < a[n]; j += a[i]){
            if(*lower_bound(a.begin() + i + 1, a.end(), j) == j)    ng[j] = true;
        }
    }
    cout << ans << endl;
}

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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll d = euclid(b, a % b, y, x);
        return y -= a / b * x, d;
    }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1)
            ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1);
        return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e)
            return Mod(1);
        Mod r = *this ^ (e / 2);
        r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);

    for (;;) {
        string s; cin >> s;
        if (s == "#") break;

        int y, m, d; cin >> y >> m >> d;

        if (y > 31 || y == 31 && m >= 5) {
            cout << "? " << y - 30 << " " << m << " " << d << endl;
        } else {
            cout << s << " " << y << " " << m << " " << d << endl;
        }
    }
}


Measured memory_bytes: 3168
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main
{
    public static void process()throws IOException
    {
        int n= ni(), arr[] = new  int[n+1], idx = n-1;
        for(int i = 1; i <= n; i++) arr[i] = ni();
        Arrays.sort(arr);

        long res = arr[n];

        for(int i = n-2; i >= 1; ){
            for(int j = 1; j <= 2 && i >= 1; j++, i--)
                res += arr[idx]*1l;
            idx--;
        }
        pn(res);
    }
 
    static final long mod=(long)1e9+7l;
    
    static FastReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new FastReader();
 
        long s = System.currentTimeMillis();
        int t=1;
        //t=ni();
        while(t-->0)
            process();
 
        out.flush();
        System.err.println(System.currentTimeMillis()-s+"ms");
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static int ni()throws IOException{return Integer.parseInt(sc.next());}
    static long nl()throws IOException{return Long.parseLong(sc.next());}
    static double nd()throws IOException{return Double.parseDouble(sc.next());}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    
    static class FastReader{ 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader(){ 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next(){ 
            while (st == null || !st.hasMoreElements()){ 
                try{ st = new StringTokenizer(br.readLine()); } catch (IOException  e){ e.printStackTrace(); } 
            } 
            return st.nextToken(); 
        } 
  
        String nextLine(){ 
            String str = ""; 
            try{ str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } 
            return str; 
        } 
    } 
}

Measured memory_bytes: 60024
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

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

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100;

int main() {
	string s;cin>>s;
	for(int i=0; i<s.size();i+=2) cout<<s[i];
	cout<<endl;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define S_MAX 20000
#define N_MAX 100000
#define M_MAX 100000
#define INF 2000000000
#define MOD 1000000007
#define SMAP(a, b) ((a)!=(b))&&((a)^=((b)^=((a)^= (b))))

typedef unsigned long long ull;
typedef   signed long long dll;

typedef struct {
	int a;
	int b;
	int c;
} moneydata;

int n, m;
int h, w;
int i, j;
int k;

int a[M_MAX];
moneydata b[N_MAX - 1];

int imos[N_MAX];

void solve(){
	int im = 0;
	ull cost = 0;
	ull byCash, byCard;

	for (i = 0; i < m-1; i++) {
		int left, right;
		if (a[i] < a[i+1]) left = a[i], right = a[i+1];
		else left = a[i+1], right = a[i];
		left--;
		right--;

		imos[left]++;
		imos[right]--;
	}

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

	for (i = 0; i < n; i++) {
		im += imos[i];
		imos[i] = im;
	}

	// for (i = 0; i < n-1; i++) printf("[%d-%d] %d\n", i, i+1, imos[i]);

	for (i = 0; i < n-1; i++) {
		byCash = (ull)b[i].a * (ull)imos[i];
		byCard = (ull)b[i].b * (ull)imos[i] + (ull)b[i].c;
		if (byCash < byCard) cost += (ull)byCash;
		else cost += (ull)byCard;
		// if (i % 1000 == 0) printf("%d/%d %llu\n", i + 1, n, cost);
	}

	printf("%llu\n", cost);

	return;
}

int main (void) {
	scanf("%d%d", &n, &m);
	for (i = 0; i < m; i++) scanf("%d", &a[i]);
	for (i = 0; i < n - 1; i++) scanf("%d%d%d", &b[i].a, &b[i].b, &b[i].c);

	solve();
	
	return 0;
}

Measured memory_bytes: 2552
c = []
for i in range(3):
    c.append(list(map(int, input().split())))

if c[0][0]-c[0][1] == c[1][0]-c[1][1] == c[2][0]-c[2][1]:
    if c[0][1]-c[0][2] == c[1][1]-c[1][2] == c[2][1]-c[2][2]:
        print("Yes")
        exit()

print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main() {
    int N,min;
    int j = 0;
    int ans= 0;
    cin >> N;
    vector<int>a(N);
    for(int i=0;i<N;i++){
        cin >> a[i];
        ans = ans + a[i] - 1;
    }
    cout << ans << endl;
}

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

using namespace std;

#define ll long long

int main() {
	string s;
	string a, b;
	ll A = 0, B = 0;
	ll ans = 0;
	cin >> s;

	for (int i = 0; i < s.size(); i++)
	{
		if (i % 2 == 0) {
			a.push_back('1');
		}
		else {
			a.push_back('0');
		}
	}
	
	for (int i = 0; i < s.size(); i++)
	{
		if (i % 2 == 0) {
			b.push_back('0');
		}
		else {
			b.push_back('1');
		}
	}

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] != a[i]) {
			A++;
		}
		
		if (s[i] != b[i]) {
			B++;
		}

	}
	
	cout << min(A, B) << endl;

}


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

int main() {
    int n, l, r;
    while(cin >> n >> l >> r, n){
        int a[55];
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        a[n] = 1;
        int cnt = 0;
        for(int y=l; y<=r; y++){
            for(int i=0;i<=n;i++){
                if(y%a[i]==0){
                    if(i%2==0)cnt++;
                    break;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}



Measured memory_bytes: 3028
import numpy as np

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

A = sorted(A)
C = np.cumsum(A)

ans = 0
cnt = 0

for i in range(N-1) :
    if C[i]*2 >= A[i+1] :
        cnt += 1
    else :
        cnt = 0

ans = cnt + 1

print(ans)
    

Measured memory_bytes: 32388
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>

using namespace std;

char tolower(char c) {
  return (c + 0x20);
}

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

    S.at(K-1) = tolower(S.at(K-1));

    cout << S << endl;
    
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    println(sum(1:parseInt(readline())-1))
end
main()

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

using namespace std;
const int MAXN = 5e5+5;
int lazy[MAXN];
int seg[MAXN];
vector<pair<int,int>> v1[MAXN];
void push(int curr){
    if(lazy[curr]){
        lazy[2*curr] += lazy[curr];
        lazy[2*curr+1] += lazy[curr];
        seg[2*curr] += lazy[curr];
        seg[2*curr+1] += lazy[curr];
        lazy[curr]= 0;
    }
}
void build(int curr,int l,int r){
    if(l==r){
        seg[curr] = 0;
        lazy[curr] = 0;
        return;
    }
    int mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr] = seg[2*curr]+seg[2*curr+1];
}
void update(int curr,int l,int r,int tl,int tr){
    
    if(l>tr||r<tl){
        return;
    }
    if(l!=r){
        push(curr);
    }
    if(tl<=l && r<=tr){
        seg[curr] ++;
        lazy[curr]++;
        return;
    }
    long long mid = (l+r)/2;
    update(2*curr,l,mid,tl,tr);
    update(2*curr+1,mid+1,r,tl,tr);
    seg[curr] = seg[2*curr]+seg[2*curr+1];
}
int query(int curr,int l,int r,int tl,int tr){
    if(l>tr||r<tl){
        return 0;
    }
    if(l!=r){
        push(curr);
    }
    if(tl<=l && r<=tr){
        return seg[curr];
    }
     long long mid = (l+r)/2;
     int a = query(2*curr,l,mid,tl,tr);
     int b = query(2*curr+1,mid+1,r,tl,tr);
     seg[curr] = seg[2*curr]+seg[2*curr+1];
     return a+b;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        int sz = r-l+1;
        v1[sz].push_back(make_pair(l,r));
    }
    build(1,1,m);
    int tot = 0;
    for(int i=1;i<=m;i++){
        for(auto x:v1[i]){
            tot++;
            
            update(1,1,m,x.first,x.second);
            //cout<<123<<" "<<x.first<<" "<<x.second<<" "<<query(1,1,m,2,2)<<endl;
        }
        int temp = 0;
        for(int j=i;j<=m;j+=i){
            
            temp+=query(1,1,m,j,j);
            
        }
        cout<<temp+(n-tot)<<endl;
    }
}

Measured memory_bytes: 21504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define UM unordered_map
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 58;
const ll MOD = 1000000007;
struct Edge
{
    ll s, t, d;
};
typedef vector<vector<Edge>> Graph;
typedef vector<pii> vpii;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

signed main()
{
    int N, C;
    cin >> N >> C;
    vpii xv;
    xv.resize(N);
    int x, v;
    REP(i, N)
    {
        cin >> x >> v;
        xv[i].first = x;
        xv[i].second = v;
    }
    //累積和
    vi migi;
    migi.resize(N);
    migi[0] = xv[0].second;
    REP(i, N - 1)
    migi[i + 1] = migi[i] + xv[i + 1].second;
    REP(i, N)
    migi[i] -= xv[i].first;
    vi hidari;
    hidari.resize(N);
    hidari[0] = xv[N - 1].second;
    REP(i, N - 1)
    hidari[i + 1] = hidari[i] + xv[N - i - 2].second;
    REP(i, N)
    hidari[i] -= C - xv[N - 1 - i].first;

    int tmp;
    //累積和dp
    vi migidp;
    migidp.resize(N);
    tmp = 0;
    REP(i, N)
    {

        chmax(tmp, migi[i]);
        migidp[i] = tmp;
    }
    vi hidaridp;
    hidaridp.resize(N);
    tmp = 0;
    REP(i, N)
    {
        chmax(tmp, hidari[i]);
        hidaridp[i] = tmp;
    }

    int ans = 0;
    REP(i, N)
    {
        //右回りでiへ行ってから、左回り貪欲
        chmax(ans, migi[i]);
        if (i < N - 1)
        {
            tmp = migi[i] - xv[i].first + hidaridp[N - 1 - (i + 1)];
            chmax(ans, tmp);
        }
        //左回りでiへ行ってから、右回り貪欲
        chmax(ans, hidari[N - 1 - i]);
        if (i > 0)
        {
            tmp = hidari[N - 1 - i] - (C - xv[i].first) + migidp[i - 1];
            chmax(ans, tmp);
        }
    }

    cout << ans << endl;
    // system("pause");
}

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

int main(){
  int n,m,X,Y;
  cin>>n>>m>>X>>Y;
  vector<int> x(n), y(m);
  for(int i=0; i <n; ++i){
    cin>>x[i];
  }
  for(int i=0; i <m; ++i){
    cin>>y[i];
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  if(max(x[n-1], X)<min(y[0], Y)) cout<<"No War\n";
  else cout<<"War\n";
  return 0;
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    string s;
    cin >> s;
    int count = 0;
    string ans1,ans2="";
    REP(i,s.size()){
        ans1 += s[i];
        if(ans2 != ans1){
            ans2 = ans1;
            count++;
            ans1 = "";
        }
    }
    COUT(count);
    return 0;
}

Measured memory_bytes: 640
/*input
2
-1000 100000
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define int long long
#define MAX 500
#define INF 1e16

struct N{
	int from , to , cap , flow;
};
struct dinic{
	int s , t , dep[MAX] , use[MAX] , res[MAX];
	vector<int> g[MAX];
	vector<N> e;
	void init(){
		REP(i , 0 , MAX) g[i].clear();
		e.clear();
	}
	void ADDE(int f , int t , int c){
		g[f].pb(e.size());
		e.pb(N{f , t , c , 0});
		g[t].pb(e.size());
		e.pb(N{t , f , 0 , 0});
	}
	int BFS(){
		MEM(use , 0) , MEM(dep , 0);
		queue<int> qu;
		qu.push(s) , dep[s] = use[s] = 1;
		while(qu.size()){
			int now = qu.front(); qu.pop();
			for(auto i : g[now]){
				N to = e[i];
				if(use[to.to] == 0 && to.cap > to.flow){
					use[to.to] = 1;
					dep[to.to] = dep[now] + 1;
					qu.push(to.to);
				}
			}
		}
		return use[t];
	}
	int DFS(int now , int lim){
		if(lim == 0 || now == t) return lim;
		int flow = 0 , tmp;
		for(int &i = res[now] ; i < g[now].size() ; i ++){
			N to = e[g[now][i]];
			if(dep[to.to] == dep[now] + 1){
				tmp = DFS(to.to , min(lim , to.cap - to.flow));
				if(tmp > 0){
					e[g[now][i] ^ 0].flow += tmp;
					e[g[now][i] ^ 1].flow -= tmp;
					flow += tmp;
					lim -= tmp;
					if(lim == 0) break;
				}
			}
		}
		return flow;
	}
	int FLOW(int s , int t){
		this -> s = s , this -> t = t;
		int flow = 0;
		while(BFS()){
			MEM(res , 0);
			flow += DFS(s , 0x3f3f3f3f);
		}
		return flow;
	}
}dc;
int n , x[MAX];
int32_t main(){
	IOS;
	cin >> n;
	REP(i , 1 , n + 1) cin >> x[i];
	int sum = 0 , s = 0 , t = n + 1;
	REP(i , 1 , n + 1){
		if(x[i] >= 0) dc.ADDE(i , t , x[i]) , sum += x[i];
		if(x[i]  < 0) dc.ADDE(s , i , -x[i]);
	}
	// DBGG("sum = " , sum);
	REP(i , 1 , n + 1) for(int j = i + i ; j <= n ; j += i)
		dc.ADDE(i , j , INF);
	cout << sum - dc.FLOW(s , t) << endl;
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
  int n,count = 0, ans = 0;
  char *s;
  scanf("%d",&n);
  s = new char[n+1];
  scanf("%s",s);

  for (int i = 0; i < n ; ++i)
    if (s[i] == '.')
      ++count;
  
  ans = count;
  for (int i = 0 ; i < n ; ++i) {
    if(s[i]=='#') ++count;
    else --count;
    ans = min(ans,count);
  }
  
  printf("%d",ans);
  delete s;
  return 0;
}


Measured memory_bytes: 512
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  const arr = lines.shift().split(' ').map(Number);
  let base_idx = partition(arr, 0, n - 1);
  arr[base_idx] = `[${arr[base_idx]}]`;
  console.log(arr.join(` `));
})();

function partition(arr, p, r) {
   let x  = arr[r];
   let i = p - 1;
   for (let j = p; j < r; j++) {
     if (arr[j] <= x) {
       i++;
       [arr[i], arr[j]] = [arr[j], arr[i]];
     }
   }
   [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
   return i + 1;
}



Measured memory_bytes: 33656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int n;
	cin>>n;
	map<int,int> mp;
	rep(i,n){
		int a;
		cin>>a;
		mp[a]++;
	}
	int ans=0;
	for(auto itr:mp){
		if(itr.fi>itr.se) ans+=itr.se;
		else ans+=itr.se-itr.fi;
	}
	cout<<ans<<endl;
}

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

int main() {
    string S; cin >> S;
    int ans[S.size()] = {};

    vector<int> L, R;
    REP(i, 0, S.size()) {
        if (S[i] == 'L') L.push_back(i);
        if (S[i] == 'R') R.push_back(i);
    }
    L.push_back(S.size()); R.push_back(S.size());

    int i = 0, j = 0;
    while (i + j < S.size()) {
        if (L[i] < R[j]) {
            if (abs(L[i] - R[j - 1]) % 2 == 1) ans[R[j - 1] + 1]++;
            else ans[R[j - 1]]++;
            i++;
        } else {
            if (abs(L[i] - R[j]) % 2 == 1) ans[L[i] - 1]++;
            else ans[L[i]]++;
            j++;
        }
    }

    REP(i, 0, S.size()) {
        if (i != S.size() - 1) cout << ans[i] << " ";
        else cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 1532
#include <stdio.h>
int main(void){
  int n, i, flag=0;
  scanf("%d", &n);
  int a[n];
  for(i=0;i<n;i++){
    scanf("%d", &a[i]);
  }
  for(i=n-1;i>=1;i--){
    if(a[i]>=a[i-1]){
    }else if(a[i]<a[i-1]&&a[i]-a[i-1]==-1){
      a[i-1]--;
    }else{
      flag++;
    }
    if(flag!=0){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  bool flag = true;
  REP(i, N){
    char tmp; cin >> tmp;
    if(tmp == 'Y') flag = false;
  }
  if(flag){
    cout << "Three" << endl;
  }else{
    cout << "Four" << endl;
  }
}

Measured memory_bytes: 256
package main

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

func main() {
	i := nextString()
	n := []byte(i)
	fmt.Println(string(n[0] + 1))
}

func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}

func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}

func nextString() string {
	return nextReader()
}

func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

func nextInt64s(n int) []int64 {
	r := make([]int64, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt64()
	}
	return r
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func Min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func MinA(arg ...int) int {
	var s = arg[0]
	for _, v := range arg {
		s = Min(s, v)
	}
	return s
}

func MaxA(arg ...int) int {
	var s = arg[0]
	for _, v := range arg {
		s = Max(s, v)
	}
	return s
}

func Abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}


Measured memory_bytes: 640
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int n  = sc.nextInt();

		int m  = sc.nextInt();
		
		System.out.println( n>m ? "safe" : "unsafe");
	}
	
	
}


Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int A,B,C,D;
cin >> A  >>B >> C>> D;
 
 if (A+B<C+D){
 cout << "Right";
 } 
  else if(A+B>C+D){
 cout << "Left";
 }
  else{
  cout << "Balanced";
  }
 
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _dbg(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _dbg(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_dbg(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const int N=2000;
using bt=bitset<N>;
bt a[N],win[N],sto[N];
int32_t main() {
    int n;
    cin>>n;
    forn(i,n){
        forn(j,i){
            char c;
            cin>>c;
            a[i][j]=c-'0';
            a[j][i]=a[i][j]^1;
        }
        win[i].set(i);
        sto[i].set(i);
    }
    for(int len=2;len<=n;++len){
        for(int i=0;i+len-1<n;++i){
            int r=i+len-1;
            if(a[i][r]){
                if((win[i]&(win[r]>>1)).any()){
                    win[i].set(r);
                    sto[r].set(i);
                }
            }
            if((a[i]&win[i]&sto[r]).any()){
                win[i].set(r);
                sto[r].set(i);
            }
        }
        for(int i=len-1;i<n;++i){
            int l=i-len+1;
            if(a[i][l]){
                if((win[i]&(win[l]<<1)).any()){
                    win[i].set(l);
                    sto[l].set(i);
                }
            }
            if((a[i]&win[i]&sto[l]).any()){
                win[i].set(l);
                sto[l].set(i);                
            }
        }
    }
    int ans=0;
    forn(i,n){
        ans+=(win[i][0]&win[i][n-1]);
    }
    cout<<ans<<'\n';


    return 0;
}


Measured memory_bytes: 1792
#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>;

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

    ll n, m;
    cin >> n >> m;

    if(n == 1) {
        if(m > 1) {
            cout << m - 2 << endl;
            return 0;
        }
    }
    if(m == 1) {
        if(n > 1) {
            cout << n - 2 << endl;
            return 0;
        }
    }
    if(n == 1 && m == 1) {
        cout << 1 << endl;
        return 0;
    }

    if(n > 1 && m > 1) {
        cout << (n-2)*(m-2) << endl;
        return 0;
    }
}


Measured memory_bytes: 3548
def get_all_index(a, value)
  index = []
  _a = a.dup
  while _a.include?(value)
    next_i = _a.index(value)
    index << next_i
    _a[next_i] = nil
  end
  index
end

n = gets.to_i
virgin = true

n.times do
  puzzle = []
  errata = []
  
  puts "" unless virgin

  9.times do
    puzzle << gets.split.map(&:to_i)
    errata << Array.new(9, true)
  end

  # checking row and column
  0.upto(8) do |i|
    0.upto(8) do |j|
      (j+1).upto(8) do |k|
        if puzzle[i][j] == puzzle[i][k]
          errata[i][j] = false
          errata[i][k] = false
        end
        if puzzle[j][i] == puzzle[k][i]
          errata[j][i] = false
          errata[k][i] = false
        end
      end
    end
  end
  
  # checking box
  box_index = []
  -1.upto(1) do |i|
    -1.upto(1) do |j|
      box_index << [i, j]
    end
  end
  [1,4,7].each do |i|
    [1,4,7].each do |j|
      cb = []
      cb_index = []
      box_index.each do |b|
        cb_index << [b[0] + i, b[1] + j]
        cb << puzzle[b[0] + i][b[1] + j]
      end
      if (temp = cb.uniq.select{ |x| cb.index(x) != cb.rindex(x) }).any?
        temp.each do |m|
          get_all_index(cb, m).each do |i|
            x, y = cb_index[i]
            errata[x][y] = false
          end
        end
      end
    end
  end

  # output
  0.upto(8) do |i|
    0.upto(8) do |j|
      if errata[i][j]
        print " #{puzzle[i][j]}"
      else
        print "*#{puzzle[i][j]}"
      end
      puts "" if j == 8
    end
  end

  virgin = false if virgin
end

Measured memory_bytes: 6128
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

const int MAX = 1e5 + 100;


const ll MOD = 1e9 + 7;
int n;

vector<ll> fac(101000);
vector<ll> fac_inv(101000);


ll mod_pow(ll x, ll n){
    ll ans = 1;
    while(n != 0){
        if(n & 1)ans = ans * x % MOD;
        x = x * x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll n, ll k){
    if(n == 0 && k == 0)return 1;
    if(n < k || n < 0)return 0;

    ll tmp = fac_inv[n - k] * fac_inv[k] % MOD;
    return tmp * fac[n] % MOD;
}

int main(){
    cin >> n;

    vector<int> mp(n + 1, -1);
    int k;
    rep(i, n + 1){
        int a;
        cin >> a;
        if(mp[a] == -1)mp[a] = i;
        else {
            k = mp[a] + n - i;
            break;
        }
    }

    fac[0] = 1;
    fac_inv[0] = 1;
    rep(i, n + 2){
        fac[i + 1] = fac[i] * (i + 1) % MOD;
        fac_inv[i + 1] = fac_inv[i] * mod_pow(i + 1, MOD - 2) % MOD;
    }

    REP(i, 1, n + 1){
        ll res = comb(n + 1, i) % MOD - comb(k, i - 1);
        if(res < 0)res += MOD;
        cout << res << endl;
    }

}



Measured memory_bytes: 3200
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;

  long count = 0;
  for(int i=1; i<S.size(); i++){
    char fi = S[i-1];
    char se = S[i];

    if(fi == se){
      if(fi == '0'){
        S[i] = '1';
      }else{
        S[i] = '0';
      }
      count++;
    }
  }

  cout << count << endl;
}

Measured memory_bytes: 512
n,m=map(int,input().split())
l,r=1,n
for i in range(m):
    ll,rr=map(int,input().split())
    if ll > l:
        l = ll
    if rr < r:
        r = rr
if l <= r:
    print(r-l+1)
else:
    print(0)

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

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;
    
    vector<int> v(n);

    for (int &x: v)
        cin >> x;

    
    for (int i = k, p = 0; i < n; ++i, p++) {
        if(v[p] < v[i]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 3988
#include<stdio.h>
#include<string.h>
  
#define MAX 1000
  
int main(){
  int i,j,m,q,x,y,c[MAX+1][MAX+1];
  char X[MAX],Y[MAX];
  
  scanf("%d",&q);
  
  for(i=0;i<strlen(X);i++)
    c[i][0] = 0;
  for(j=0;j<strlen(Y);j++)
    c[0][j] = 0;
  
  for(m=0;m<q;m++){
    scanf("%s",X);
    scanf("%s",Y);
    x = strlen(X);
    y = strlen(Y);
    for(i=0;i<x;i++)
      c[i][0] = 0;
    for(j=0;j<y;j++)
      c[0][j] = 0;
  
    for(i=1;i<=x;i++){
      for(j=1;j<=y;j++){
    if(X[i-1] == Y[j-1])c[i][j] = c[i-1][j-1] + 1;
    else if(c[i-1][j] >= c[i][j-1])c[i][j] = c[i-1][j];
    else c[i][j] = c[i][j-1];
      }
    }
    printf("%d\n",c[x][y]);
  }
  
  return 0;
}

Measured memory_bytes: 4944
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

typedef std::vector< int > vi;
typedef std::pair< int, int > pii;

bool comp(pii lhs, pii rhs)
{
  return lhs.first > rhs.first;
}


int main(int argc, char* argv[])
{
  int n;
  std::string str;
  std::vector< pii > red;
  std::vector< pii > blue;  

  std::vector< pii >::iterator itr;
  std::vector< pii >::iterator itb;  

  getline(std::cin, str);
  sscanf(str.c_str(), "%d", &n);

  for (int i = 0; i < n; i++) {
    int a, b;
    pii tmp;
    getline(std::cin, str);
    sscanf(str.c_str(), "%d %d", &a, &b);
    tmp.first = a;
    tmp.second = b;
    red.push_back(tmp);
  }
  
  for (int i = 0; i < n; i++) {
    int c,d;
    pii tmp;
    getline(std::cin, str);
    sscanf(str.c_str(), "%d %d", &c, &d);
    tmp.first  = c;
    tmp.second = d;
    blue.push_back(tmp);
  }

  // test
  //for (itr = red.begin(); itr != red.end(); itr++) {
  //  std::cout << itr->first << " " << itr->second << std::endl;
  //}

  // test
  //for (itr = blue.begin(); itr != blue.end(); itr++) {
  //  std::cout << itr->first << " " << itr->second << std::endl;
  //}

  //std::cout << std::endl;
  
  std::sort(red.begin(), red.end(), comp);

  // test
  //std::cout << "sorted red" << std::endl;
  //for (itr = red.begin(); itr != red.end(); itr++) {
  //  std::cout << itr->first << " " << itr->second << std::endl;
  //}

  // test
  //std::cout << "sorted blue" << std::endl;  
  //for (itb = blue.begin(); itb != blue.end(); itb++) {
  //  std::cout << itb->first << " " << itb->second << std::endl;
  //}

  //std::cout << "execution" << std::endl;  
  int ans = 0;
  for (itr = red.begin(); itr != red.end(); itr++) {
    int min_blue_y = 999999;
    std::vector< pii >::iterator it = blue.end();
    for (itb = blue.begin(); itb != blue.end(); itb++) {
      if (itr->first < itb->first && itr->second < itb->second && itb->second < min_blue_y) {
	min_blue_y = itb->second;
	it = itb;
	//std::cout << "*" << itr->first << " " << itr->second << " " << it->first << " " << it->second << std::endl;
      }
    }
    if (it != blue.end()) {
      ans++;
      //std::cout << itr->first << " " << itr->second << " " << it->first << " " << it->second << std::endl;
      it->second = -1;
    }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の機能を「全て」読み込むための命令
#define rep(i,n) for(int i=0; i<(n); ++i)
#define cout(x) cout<<(x)<<endl
#define all(v) v.begin(), v.end()
using namespace std;
//型エイリアス
using vi = vector<int>;
using ll = long long;
using P = pair<int,int>;
using Mat = vector<vector<int>>;
const ll inf = 1e18;
const int N = 2e5+10;

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];

    int idx = 0;
    int ans = 0;
    rep(i,n-1){
        if(a[idx]==2){
            ans = i+1;
            cout(ans);
            return 0;
        }
        idx = a[idx] - 1;
    }
    cout(-1);

    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cctype>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;while(isspace(c)){c=gcu();}if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m?-n:n;}
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(bool b) {pcu('0'+b);}
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

int main() {
	for (int n, m; n = in(), m = in();) {
		vector<int> v(n);
		for (int &x: v)
			x = in();
		sort(v.rbegin(), v.rend());
		int p = 0;
		for (int i = 0; i < n; i++)
			if ((i + 1) % m)
				p += v[i];
		outl(p);
	}
}


Measured memory_bytes: 2456
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    H, N = Scanner.map_int()
    A, B = [0 for _ in range(N)], [0 for _ in range(N)]
    for i in range(N):
        a, b = Scanner.map_int()
        A[i] = a
        B[i] = b
    dp = [0] * (H + 1)
    for i in range(1, H + 1):
        mp = INF
        for j in range(N):
            if i - A[j] < 0:
                mp = min(mp, B[j])
            else:
                mp = min(mp, dp[i - A[j]] + B[j])
            pass
        dp[i] = mp
    print(dp[H])


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 63212
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

def solve(N, ABs):
    Cs = []
    for n in range(N):
        a, b = ABs[n]
        Cs.append((a + b, a, b))
    Cs.sort()
    Cs.reverse()
    
    taka = 0
    aoki = 0
    for i, c in enumerate(Cs):
        if i % 2 == 0:
            taka += Cs[i][1]
        else:
            aoki += Cs[i][2]
    return taka - aoki

def main():
    N = int(input())
    ABs = []
    for n in range(N):
        a, b = map(int, input().split())
        ABs.append((a, b))
    print(solve(N, ABs))
main()

# def testcase(N, ABs, expected):
#     mine = solve(N, ABs)
#     if mine != expected:
#         print("error!")
#         print("  N = ", N)
#         print("  ABs = ", ABs)
#         print("  expected = ", expected)
#         print("  mine = ", mine)

# testcase(3, [(10,10),(20,20),(30,30)], 20)
# testcase(3, [(20,10),(20,20),(20,30)], 20)
# testcase(6, [(1,1000000000)]*6, -2999999997)
# testcase(3, [(10,1000),(10,10),(30,30)], 20 - 30)
# testcase(4, [(10,1000),(10,10),(30,30)], 20 - 30)



Measured memory_bytes: 30628
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10, MOD = 1e9 + 7;

vector <int> primes;
bool isPrime[MAXN];
int cnt[MAXN];

int solve(int n){
	int mid, l = 0, r = 1000;
	while(r - l > 1){
		mid = (r + l) / 2;
		if((mid * (mid + 1)) / 2 <= n) l = mid;
		else r = mid;
	}
	return l;
}


int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	fill(isPrime, isPrime + MAXN, 1);
	isPrime[1] = 0;
	for(long long i = 2; i < MAXN; i++){
		if(isPrime[i]){
			for(long long j = i; i * j < MAXN; j++){
				isPrime[j * i] = 0;
			}
			primes.push_back(i);
		}
	}
	long long ans = 0;
	long long n;
	cin >> n;
	for(int i : primes){
		while(n % i == 0){
			cnt[i]++;
			n /= i;
		}
	}
	for(int i = 2; i < MAXN; i++){
		if(cnt[i] != 0)
			ans += solve(cnt[i]);
	}
	if(n != 1) ans++;
	cout << ans << "\n";
}

Measured memory_bytes: 4844
N = int(input())
S1 = input()
S2 = input()

m = 1000000007

if S1[0] == S2[0]:
    result = 3
else:
    result = 6
x = 0
W = len(S1)
while x < W:
    if S1[x] == S2[x]:
        if x + 1 == W:
            break
        result *= 2
        result %= m
        x += 1
    else:
        if x + 2 == W:
            break
        if S1[x + 2] != S2[x + 2]:
            result *= 3
            result %= m
        x += 2
print(result)


Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

int power(int x,int n,int mod){
    //(x^n)%mod
    int result=1;
    while(n){
        if(n%2)
            result=(result*x)%mod;
        x=(x*x)%mod;
        n/=2;
    }
    return result;
}


int curr;
int money;
int maxProfit(vector<int> &prices) {
    int ans = 0;
    int n = prices.size();
    if(n == 0)return 0;
    for(int i = 1; i < n; i++) {
        curr=money/prices[i-1];
        if(prices[i]>prices[i-1]){
            money+=(prices[i]-prices[i-1])*curr;
        }
    }
    return money;

}


int32_t main() {

    fast

    int n;
    cin>>n;

    vector<int>arr(n);

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    money=1000;
    int curr=1000/arr[0];
    cout<<maxProfit(arr)<<endl;





    return 0;
}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
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; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

template<class T>struct dijkstra{//T=int or ll
  struct Node{
    vector<T> edges_to;
    vector<T> edges_cost;
    bool done;
    T cost=-1;
  };
  vector<Node> graph;
  void init(T N){
    graph.resize(N);
  }
  void add(T from, T to, T cost){
    graph[from].edges_to.push_back(to);
    graph[from].edges_cost.push_back(cost);
  }
  void shortest(T start){
    priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>> d;
    d.push(make_pair(0,start));
    while(!d.empty()){
      pair<T,T> p = d.top();
      d.pop();
      Node &point = graph[p.second];
      if(point.done) continue;
      point.done = true;
      point.cost = p.first;
      for(T i = 0; i < (T)point.edges_to.size(); i++){
        if(graph[point.edges_to[i]].done)continue;
        d.push(make_pair(point.cost+point.edges_cost[i],point.edges_to[i]));
      }
    }
  }
};

int main() {
    ll N,M,s,t;
    cin>>N>>M>>s>>t;
    s--;
    t--;
    dijkstra<ll> yen,snuuk;
    yen.init(N);
    snuuk.init(N);
    for(ll i = 0; i < M; i++){
        ll u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;
        v--;
        yen.add(u,v,a);
        yen.add(v,u,a);
        snuuk.add(u,v,b);
        snuuk.add(v,u,b);
    }
    yen.shortest(s);
    snuuk.shortest(t);
    vector<ll> cost(N);
    for(ll i = 0; i < N; i++){
        cost[i]=yen.graph[i].cost+snuuk.graph[i].cost;
    }
    for(ll i = N-1; i > 0; i--){
        chmin(cost[i-1],cost[i]);
    }
    for(auto x:cost){
        cout<<1000000000000000LL-x<<endl;
    }
}

Measured memory_bytes: 29556
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <functional>
#define rep(i,j,n) for(i=j;i<(n);i++)
#define rrep(i,j,n) for(i=j;i>(n);i--)
typedef long long int lli;
#define N 1000000007

using namespace std;

int main(){
    string s,ans="NO";
    lli i,j;
    map<char,lli> map;
    cin>>s;
    rep(i,0,s.size()){
        map[s[i]]++;
    }
    if((abs(map['a']-map['b'])<=1)&&(abs(map['a']-map['c'])<=1)&&(abs(map['c']-map['b'])<=1)){
        ans="YES";
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 512