akhauriyash/Code-Regression huggingface dataset:
use std::io::Read;

const MOD: usize = 1_000_000_007;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let k: usize = iterator.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..n)
        .map(|_| iterator.next().unwrap().parse().unwrap())
        .collect();

    // b[i] = iの個数
    let mut b: Vec<usize> = vec![0; 2002];
    for &ai in a.iter() {
        b[ai] += 1;
    }

    // c[i] = iより大きい数の個数
    let mut c: Vec<usize> = vec![0; 2002];
    for i in (1..2001).rev() {
        c[i] = b[i + 1] + c[i + 1];
    }

    // 整数列A単体での個数
    let mut t = 0;
    for i in 1..n {
        for j in 0..i {
            if a[j] > a[i] {
                t += 1;
            }
        }
    }

    let mut ans = t * k;
    ans %= MOD;

    for i in 0..2001 {
        ans = (ans + b[i] * (c[i] * ((k * (k - 1) / 2) % MOD) % MOD) % MOD) % MOD;
    }

    return ans.to_string();
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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

#define keta setprecision(10) //10桁表示


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

	int h, w, k;
	cin >> h >> w >> k;
	vector<string> s(h);
	vector<vector<int>> ans(h, vector<int>(w, 0));
	rep(i, h)
	{
		cin >> s[i];
	}
	int n = 0;
	vector<int> notB(h, 0);

	rep(i, h)
	{
		rep(j, w)
		{
			if (s[i][j] == '#')
			{
				n++;
			}
		}
		if (n == 0)
		{
			notB[i] = 1;
		}
		n = 0;
	}

	int num = 1;
	vector<int> rNum(h, 0);

	rep(i, h)
	{
		rep(j, w)
		{
			if (notB[i] == 0)
			{
				if (s[i][j] == '#' && rNum[i] != 0)
				{
					num++;
				}
				else if (s[i][j] == '#' && rNum[i] == 0)
				{
					rNum[i]++;
				}
				ans[i][j] = num;
			}
			else
			{
				break;
			}
		}
		if(notB[i]==0)
			num++;
	}

	rep(i, h-1)
	{
		rep(j, w)
		{
			if (ans[i+1][j] == 0)
			{
				ans[i+1][j] = ans[i][j];
			}
		}
	}
	for (int i = h-1; i >0; i--)
	{
		for (int j = 0; j < w; j++)
		{
			if (ans[i-1][j] == 0)
			{
				ans[i-1][j] = ans[i][j];
			}
		}
	}

	rep(i, h)
	{
		rep(j, w-1)
		{
			cout << ans[i][j] << " ";
		}
		cout << ans[i][w - 1] << endl;
	}

	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")  // disable
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define lll __int128
#define lp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define vec(v, type, sz) vector<type> v(sz)
#define in(v) \
    for (auto &i : v) cin >> i
#define all(v) v.begin(), v.end()
#define prv(v)                         \
    for (auto i : v) cout << i << " "; \
    cout << "\n"
#define MOD 1000000007
#define INF 1000000000
#define INFL 1000000000000000000ll
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define vi vector<int>
#define vl vector<ll>
#define vii(v, n, m, val) vector<vector<int>> v(n, vector<int>(m, val))
#define viii(v, i, j, k, val)        \
    vector<vector<vector<int>>> v(i, \
                                  vector<vector<int>>(j, vector<int>(k, val)))
#define pii pair<int, int>
#define pb push_back
#define file_io                       \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
#define testcases \
    int tcc;      \
    cin >> tcc;   \
    for (int tc = 1; tc <= tcc; tc++)
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while (!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
    cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if (idx > 0)
        cerr << ", ";
    else
        cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss;
    ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef DB
#define debug(...) \
    debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
    fast_io;
    int n,k; cin>>n>>k;
    vector<int> v(n+1);
    lp(i,0,k){
    	int d; cin>>d;
    	while(d--){
    		int t; cin>>t;
    		v[t]++;
    	}
    }
    int ans=0;
    lp(i,1,n+1){
    	if(v[i]==0) ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3648
#include <stdio.h>
int main()
{
  int S,h,m,s,x ;
  scanf("%d",&S);
    h=S/3600;
    x=S%3600;
    m=x/60;
    s=x%60;
    printf("%d:%d:%d\n",h,m,s);

  return 0;
}

Measured memory_bytes: 592
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
out = [int(input()) for _ in range(D)]

sat = 0
last = [0] * 26
for d in range(D):
    assert(1 <= out[d] and out[d] <= 26)
    j = out[d] - 1
    last[j] = d + 1
    for i in range(26):
        sat -= (d + 1 - last[i]) * c[i]
    sat += s[d][j]
    print(sat)

Measured memory_bytes: 9184
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int h, w;
vector<string> grid;
vector<vector<bool>> isVisited;

using P = pair<int, int>;

template <typename F>
void forNeighbor4(int x, int y, F f)
{
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if (abs(dx) + abs(dy) == 1) {
                f(x + dx, y + dy);
            }
        }
    }
}

P dfs(int x, int y)
{
    isVisited[x][y] = true;

    int white = 0, black = 0;

    forNeighbor4(x, y, [&](int nx, int ny) {
        if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] != grid[x][y] && !isVisited[nx][ny]) {
            int a, b;
            tie(a, b) = dfs(nx, ny);
            white += a;
            black += b;
        }
    });
    (grid[x][y] == '.' ? white : black)++;

    return make_pair(white, black);
}

int main()
{
    cin >> h >> w;

    grid.resize(h);
    rep(i, h)
    {
        cin >> grid[i];
    }

    isVisited = vector<vector<bool>>(h, vector<bool>(w, false));

    int64_t result = 0;
    rep(i, h) rep(j, w)
    {
        if (!isVisited[i][j]) {
            int white, black;
            tie(white, black) = dfs(i, j);
            result += (int64_t)white * black;
        }
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 20480
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 * 2 + 10;
typedef long long ll;

ll st[N];
int vis[N];

int main()
{
    ll n,a,p;
    cin >> n >> a >> p;
    memset(vis,-1,sizeof vis);
    int i = 0;
    ll j = a;
    // 找到环的入口
    for(i = 0, j = a; vis[j] == -1; i ++, j = j * j % p)
        vis[j] = i,st[i] = j;
    ll ans = 0,sum = 0;
    // 表示无环
    if(n == vis[j])
    {
        for(int k = 0; k < n; k ++) ans += st[k];
        cout << ans << endl;
        return 0;
    }
    
    // 环的前驱
    for(int k = 0; k < vis[j]; k ++) ans += st[k];
    
    // 环的后继
    for(int k = 0; k < (n - vis[j]) % (i - vis[j]); k ++) ans += st[k + vis[j]];

    // 环的内部
    for(int k = vis[j]; k < i; k ++) sum += st[k];
    
    cout << ans + ((n - vis[j]) / (i - vis[j]) * sum);
    
}

Measured memory_bytes: 4752
#include <bits/stdc++.h>
#define ll long long int
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define inputv(a) forall(i,0,a.size()) cin>>a[i]
#define outputv(a) for(auto i:a) cout<<i<<" ";br;
#define fs first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define minv(a) *min_element(all(a))
#define maxv(a) *max_element(all(a))
#define br cout<<"\n"
using namespace std;
int dr[]={1,-1,0,0};
int dc[]={0,0,1,-1};
ll mod=1000000007;
ll po(ll x,ll n){
    ll res = 1;
    while(n>0){
        if(n%2==1)
            res = ((res)*(x));
        x = (x*x);
        n = n/2;
    }
    return res;
}
ll ceil(ll x,ll y)
{
    if(x%y==0)
        return x/y;
    else
        return(x/y)+1;
}
ll reverse(ll num)
{
     ll n, reversedNumber = 0, remainder;
     n=num;
    while(n != 0)
    {
        remainder = n%10;
        reversedNumber = reversedNumber*10 + remainder;
        n /= 10;
    }
    return reversedNumber;
}
bool divisor(ll n)
{
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   string s,t;
   cin>>s>>t;
   ll ans=0;
   for(ll i=0;i<s.size();i++)
   {
       if(s[i]!=t[i])
        ans++;
   }
   cout<<ans;
	return 0;
}


Measured memory_bytes: 3892
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+6;//!
struct permutain{
    int a[N];
    permutain(){memset(a,0,sizeof a);}
    int& operator [](int x){return a[x];}
}p,q,ip,iq,A,B,ans;
int n,k;
permutain operator *(permutain a,permutain b){
    permutain c;
    for(int i=1;i<=n;i++)
        c[i]=a[b[i]];
    return c;
}
permutain inv(permutain a){
    permutain b;
    for(int i=1;i<=n;i++)
        b[a[i]]=i;
    return b;
}
permutain operator ^(permutain a,int b){
    permutain c;
    for(int i=1;i<=n;i++)
        c[i]=i;
    while(b){
        if(b&1)
            c=c*a;
        a=a*a;
        b>>=1;
    }
    return c;
}
void Print(permutain x){
    for(int i=1;i<=n;i++)
        printf("%d ",x.a[i]);
    puts("");
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&q[i]);
    ip=inv(p);
    iq=inv(q);
    int f=(k-1)/6,g=k-f*6;
    permutain h=q*ip*iq*p;
    A=h^f;
    if(g==1){
        B=p;
    }
    else if(g==2){
        B=q;
    }
    else if(g==3){
        B=q*ip;
    }
    else if(g==4){
        A=A*q;
        B=ip;
    }
    else if(g==5){
        A=A*q*ip;
        B=iq;
    }
    else{
        A=A*q*ip;
        B=iq*p;
    }
    ans=A*B*inv(A);
    Print(ans);
}


Measured memory_bytes: 23040
a = gets.to_i
henkan = "abcdefghijklmnopqrstuvwxyz"
aans = []
 
while a > 0
  a -= 1
  amari = a % 26.to_f
  shou = a / 26
  ans = henkan[amari]
  aans.push(ans)
  a = shou
end
 
puts aans.reverse.join

Measured memory_bytes: 14320
fun main(args: Array<String>) {
    val s = readInputLine().toCharArray()
    
    var ans = 0
    var befChar = s[0]
    
    for (c in s) {
        if (c != befChar) {
            ans++
            befChar = c
        }
    }
    
    println(ans)
}
 
fun readInputLine(): String {
    return readLine()!!
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int tot=M*1900+(N-M)*100;
	cout<<(tot<<M)<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt(),a=s.nextInt(),b=s.nextInt();
		
		int r=0,t=0,u=0;
		
		for(int i=0;i<n;++i) {
			int v=s.nextInt();
			if(v<=a)
				++r;
			else if(v<=b)
				++t;
			else
				++u;
		}
		System.out.println(Math.min(r,Math.min(t,u)));
	}
}


Measured memory_bytes: 23124
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
    int n, i, s, g, a[100];
    for(i=0;i < 10;i++)
    scanf("%d", &a[i]);
    sort(a, a+i);
    printf("%d\n%d\n%d\n", a[9], a[8], a[7]);
    return 0;
    }

Measured memory_bytes: 1204
n,m = map(int,input().split())
h = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]

ans = [1 for i in range(n)]

for i in range(m):
    if h[ab[i][0]-1] > h[ab[i][1]-1]:
        ans[ab[i][1]-1] = 0
    elif h[ab[i][0]-1] < h[ab[i][1]-1]:
        ans[ab[i][0]-1] = 0
    elif h[ab[i][0]-1] == h[ab[i][1]-1]:
        ans[ab[i][1]-1] = 0
        ans[ab[i][0]-1] = 0

print(ans.count(1))

Measured memory_bytes: 32024
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s; cin >> s;
  char ch = s[s.length()-1];
  switch(ch)
  {
    case '0':
    case '1':
    case '6':
    case '8':
      cout << "pon";
      break;
    case '3':
      cout << "bon";
      break;
    default:
      cout << "hon";
      break;
  }
  return 0;
}

Measured memory_bytes: 3504
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * (y / gcd(x, y)); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto A = RD;
	auto B = RD;

	writeln(lcm(A, B));
	stdout.flush;
	debug readln;
}

Measured memory_bytes: 256
N = int(input())
X = [100] * 26
for _ in range(N):
    S = input()
    A = [0] * 26
    for s in S:
        A[ord(s) - 97] += 1
    for i in range(26):
        X[i] = min(X[i], A[i])

ans = ""
for i in range(26):
    ans += chr(i+97) * X[i]

print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <functional>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define FORCLS(i,a,b) for(int i = (a); i <= (b); i++)
#define REPCLS(i,n) FORCLS(i,1,n)

using Int = long;

Int n,l,t;
const Int ARI_MAX = 100005;
Int x[ARI_MAX];
Int w[ARI_MAX];

void solve() {
    cin >> n >> l >> t;

    REP(i, n) {
        cin >>x[i] >> w[i];
        w[i] = (w[i] == 2) ? -1 : 1;
    }
    Int crossCnt = 0;
    FOR(i, 1, n){
        if (w[0] != w[i]){
            Int d = (-(x[0] * w[0]) -(x[i] * w[i]) + l) % l;
            if (d <= (2 * t)){
                crossCnt += (2 * t - d) / l + 1;
            }
        }
    }
    Int id = (((crossCnt * w[0]) % n ) + n) % n;
    REP(i, n){
        x[i] = (((x[i] + t * w[i]) % l) + l) % l;
    }
    Int idX = x[0];
    
    sort(x, x + n);
    Int idXrank;
    
    if (w[0] == -1) {
        for(idXrank = 0; idXrank < n; idXrank++){
            if (x[idXrank] == idX) break;
        }
    }
    else {
        for(idXrank = n-1; idXrank >= 0; idXrank--) {
            if (x[idXrank] == idX) break;
        }
    }
    REP(i, n){
        cout << x[(i - (id - idXrank) + n) % n] << endl;
    }

    return;
}

#ifdef DEBUG
#define MAIN hoge
#else
#define MAIN main
#endif

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


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

template<typename T> T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }

const int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int N, K;
    cin >> N >> K;
    vi p(N);
    rep(i, N) cin >> p[i];

    vector<long double> E(N), ES(N+1, 0.0);

    rep(i, N) {
        E[i] = p[i] + 1;
        E[i] /= 2;
    }

    rep(i, N) {
        ES[i+1] = ES[i] + E[i];
    }

    long double res = -1;

    for (int i = 0; i + K <= N; i++) {
        auto t = ES[i+K] - ES[i];
        res = max(res, t);
    }

    cout << fixed << setprecision(10) << res << endl;
    return 0;
}


Measured memory_bytes: 7296
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        String delimiter = "";
        for (int i = n - 1; i >= 0; i--) {
            System.out.printf(delimiter + a[i]);
            delimiter = " ";
        }
        System.out.println();
        sc.close();
    }
}


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

int main(){
  int a,b,d,r;
  double f;

  cin >> a >> b;
  d = a/b;
  r = a%b;
  f = (double)a/(double)b;

  cout << d << " " << r << " " << fixed << setprecision(6) << f << endl;
  return 0;
}


Measured memory_bytes: 3288
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s="CODEFESTIVAL2016", s1;
    cin>>s1;
    int cnt=0;
    for(int i=0; i<16; ++i){
      if(s[i]!=s1[i])
        ++cnt;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
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 (a > b) { a = b; return 1; } return 0; }

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(n),b(m);
    rep(i,n){
        cin >> a[i];
        if(i>0)a[i] += a[i-1];
    }
    rep(i,m){
        cin >> b[i];
        if(i>0)b[i] += b[i-1];
    }
    ll ans = upper_bound(ALL(b),k) - b.begin();
    rep(i,n){
        // a を i冊読む
        ll tmp = a[i];
        if(tmp>k)continue;
        ll p = upper_bound(ALL(b),k - tmp) - b.begin();
        chmax(ans,i + 1 + p);
    }
    cout << ans << endl;
}

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

int main() {
  int H,W;
  cin>>H>>W;
  int U[H][W]={0},D[H][W]={0},L[H][W]={0},R[H][W]={0};
  char P[H][W];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>P[i][j];
    }
  }
  
  //LR
  for(int i=0;i<H;i++){
    int cur=1;
    for(int j=0;j<W;j++){
      if(P[i][j]=='#'){
        L[i][j]=0;
        cur=1;
      }
      else{
        L[i][j]=cur;
        cur++;
      }
    }
  }
  
  for(int i=0;i<H;i++){ 
    int cur=1;
    for(int j=W-1;j>=0;j--){
      if(P[i][j]=='#'){
        R[i][j]=0;
        cur=1;
      }
      else{
        R[i][j]=cur;
        cur++;
      }
    }        
  }
  
  //UD
  for(int i=0;i<W;i++){
    int cur=1;
    for(int j=0;j<H;j++){
      if(P[j][i]=='#'){
        U[j][i]=0;
        cur=1;
      }
      else{
        U[j][i]=cur;
        cur++;
      }
    }
  }
  
  for(int i=0;i<W;i++){
    int cur=1;
    for(int j=H-1;j>=0;j--){
      if(P[j][i]=='#'){
        D[j][i]=0;
        cur=1;
      }
      else{
        D[j][i]=cur;
        cur++;
      }
    }        
  }
  
  int cnt=0;
  int maxcnt=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cnt=U[i][j]+D[i][j]+R[i][j]+L[i][j]-3;
      maxcnt=max(maxcnt,cnt);
    }
  }
  cout<<maxcnt<<endl;

 return 0;
}

Measured memory_bytes: 69968
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    S: str = input().strip()
    T: str = input().strip()
    last_i = -1
    for i in range(len(S)-len(T)+1):
        matches = True
        for t in range(len(T)):
            s = i+t
            if S[s] == '?':
                continue
            elif S[s] != T[t]:
                matches = False
                break
        if matches:
            last_i = i
    if last_i == -1:
        return 'UNRESTORABLE'
    answer = list(S)
    for i in range(last_i, last_i+len(T)):
        answer[i] = T[i-last_i]
    for i in range(len(S)):
        if answer[i] == '?':
            answer[i] = 'a'
    return ''.join(answer)


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 74760
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const double pi = acos(-1);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct point {int x, y; };
point operator + (point a, point b) {return (point) {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) {return (point) {a.x - b.x, a.y - b.y}; }
point operator * (point a, int b) {return (point) {a.x * b, a.y * b}; }
long long operator * (point a, point b) {return 1ll * a.x * b.y - 1ll * a.y * b.x; }
bool operator < (point a, point b) {
	if (a.y == b.y) return a.x < b.x;
	else return a.y < b.y;
}
long long dist(point a) {return 1ll * a.x * a.x + 1ll * a.y * a.y; }
int n, m, q; map <point, double> mp;
point a[MAXN], b[MAXN], fp;
bool cmp(point a, point b) {
	long long tmp = (a - fp) * (b - fp);
	if (tmp == 0) return dist(a - fp) < dist(b - fp);
	else return tmp > 0;
}
double PolarAngle(point x) {
	return atan2(x.y, x.x);
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i].x), read(a[i].y);
		b[i] = a[i];
	}
	for (int i = 2; i <= n; i++)
		if (a[i] < a[1]) swap(a[i], a[1]);
	fp = a[1];
	sort(a + 2, a + n + 1, cmp);
	a[n + 1] = a[1];
	int top = 1;
	for (int i = 2; i <= n + 1; i++) {
		while (top >= 2 + (i == n + 1) && (a[top] - a[top - 1]) * (a[i] - a[top - 1]) <= 0) top--;
		a[++top] = a[i];
	}
	a[0] = a[top - 1];
	for (int i = 1; i <= top - 1; i++) {
		double res = PolarAngle(a[i + 1] - a[i]) - PolarAngle(a[i] - a[i - 1]);
		if (res < 0) res += 2 * pi;
		mp[a[i]] = res / (2 * pi);
	}
	for (int i = 1; i <= n; i++)
		printf("%.10lf\n", mp[b[i]]);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+100;
char s[N],t[N],ans[N];
int n,m;
int main(){
    scanf("%d %s %s",&n,s,t);
    for(int i=0;i<n*2;++i){
        if(i&1) ans[i]=t[i>>1];
        else ans[i]=s[i>>1];
    }
    printf("%s\n",ans);
}

Measured memory_bytes: 256
import qualified Data.IntMap as Map
type Primes = Map.IntMap Integer

main :: IO ()
main = do
    n <- readLn
    print $ solve n

solve :: Integer -> Integer
solve n = a `mod` b
    where
        a = Map.fold (*) 1 ps'
        b = 10^(9::Integer)+7
        ps = primes $ product [1..n]
        ps' = Map.map (+1) ps

primes :: Integer -> Primes
primes 1 = Map.empty
primes n = Map.unionWith (+) p1 (primes n')
    where
        v = factor1 n
        p1 = Map.singleton (fromInteger v) 1
        n' = n `div` v

factor1 :: Integer -> Integer
factor1 n = head ks
    where ks = [x | x <- 2:[3,5..], n `mod` x == 0]


Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
struct mint {
    long long x;
    mint(long long _x=0):x((_x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint modpow(long long t) const {
        if (!t) return 1;
        mint a = modpow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return modpow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

mint dp[2020][2020];

int N,M;
void debug(){
    rep(i,N+1){
        rep(j,M+1){
        cerr<<dp[i][j].x<<" ";
        }
        cerr<<endl;
    }

}
//dp[i][j]: Sからi文字、Tからj文字使ったときの部分列の数
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin>>N>>M;
    vector<ll> S(N);
    rep(i,N)cin>>S[i];
    vector<ll> T(M);
    rep(i,M)cin>>T[i];
    rep(i,N+1)dp[i][0] = 1;
    rep(j,M+1)dp[0][j] = 1;
    rep(i,N)rep(j,M){
        if(S[i] == T[j]){
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1];
        }
        else{
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j];
        }
        //cerr<<i<<" "<<j<<endl;
        //debug();
        //cerr<<endl;
    }
    cout<<dp[N][M].x<<endl;
}

Measured memory_bytes: 32128
from collections import deque
newarr = input()
newarr = newarr.split()
n = int(newarr[0])
m = int(newarr[1])
dicts = {}
ans = [0] * (n + 1)
for line in range(m):
    newarr = input()
    newarr = newarr.split()
    froom = int(newarr[0])
    sroom = int(newarr[1])
    if froom not in dicts:
        dicts[froom] = []
    if sroom not in dicts:
        dicts[sroom] = []
    dicts[froom].append(sroom)
    dicts[sroom].append(froom)
queue = deque([])
if 1 not in dicts:
    print("No")
else:
    ans[1] = 1
    curarr = dicts[1]
    for i in curarr:
        queue.append(i)
        ans[i] = 1 
    while queue:
        curitem = queue.popleft()
        if curitem not in dicts:
            continue 
        curarr = dicts[curitem]
        for i in curarr:
            if ans[i] == 0:
                ans[i] = curitem 
                queue.append(i)

    finalans = []
    flag = 0 
    for i in range(2, n + 1):
        if i == 0 :
            flag = 1 
            break 
        finalans.append(ans[i])
    if flag == 1:
        print("No")
    else:
        print("Yes")
        for i in finalans:
            print(i)




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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Read();
            var suc = false;
            if (S[0] == S[1] && S[2] == S[3] && S[0] != S[2]) suc = true;
            else if (S[0] == S[2] && S[1] == S[3] && S[0] != S[1]) suc = true;
            else if (S[0] == S[3] && S[1] == S[2] && S[0] != S[1]) suc = true;

            Console.WriteLine(suc ? "Yes" : "No");
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 13140
#include <stdio.h>

int a,A[50];

int solve(int,int);

int main ()
{
  int x,M,i;
  scanf ("%d",&a);
  for(i=0;i<a;i++) scanf("%d",&A[i]);
  scanf("%d",&x);
  for(i=0;i<x;i++)
    {
      scanf("%d",&M);
      if(solve(0,M)) printf("yes\n");
      else printf("no\n");
    }
  return 0;
}

int solve (int i,int m)
{
  if(m==0)
    return 1;
  if(i>=a)
    return 0;
  int res = solve(i+1,m) || solve(i+1,m-A[i]);
  return res;
}



Measured memory_bytes: 2104
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int a, b; cin >> a >> b;
  cout << (b % a == 0 ? a + b : b - a) << '\n';
  return 0;
}


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

using namespace std;

int main() {
  char s[3][13];
  scanf("%s%s%s", s[0], s[1], s[2]);
  printf("%c%c%c\n", toupper(s[0][0]), toupper(s[1][0]), toupper(s[2][0]));
}


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

int main() {
  int N;
  cin >> N;
  vector<string> result(N);
  for (int i=0; i<N; i++){
      cin >> result.at(i);
  }
  int a,b,c,d;
  a=0;
  b=0;
  c=0;
  d=0;
  for (int i=0; i<N; i++){
      if (result.at(i)=="AC"){
          a++;
      }
      else if(result.at(i)=="WA"){
          b++;
      }
      else if(result.at(i)=="TLE"){
          c++;
      }
      else{
          d++;
      }
  }
  cout<<"AC x "<<a<<endl;
  cout<<"WA x "<<b<<endl;
  cout<<"TLE x "<<c<<endl;
  cout<<"RE x "<<d<<endl;
  }


Measured memory_bytes: 6400
a, b, c, x, y = map(int, input().split())

res = 0

if x == y:
    res = min(a * x + b * y, c * x * 2)

elif x > y:
    res = min(a * x + b * y, a * (x - y) + c * y * 2, c * x * 2)

else:
    res = min(a * x + b * y, b * (y - x) + c * x * 2, c * y * 2)

print(res)  

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int mx=1e5+777;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int x; cin>>x;
	vector<bool> poss(mx,false);
	poss[0]=true;
	for (int t=100; t<=105; t++)
		for (int i=0; t+i<mx; i++)
			if(poss[i])
				poss[i+t]=true;
	cout<<poss[x]<<"\n";
	return 0;
}


Measured memory_bytes: 256
#pypyは内包表記使わない
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input().rstrip()
    T = input().rstrip()
    s = len(S)
    t = len(T)
    if s<t:
        print('UNRESTORABLE')
        exit()
    else:
        for i in range(s, t-1, -1):
            match = S[i-t:i]
            for j in range(t):
                if match[j] != '?' and T[j] != match[j]:
                    break
            else:
                S = S[:i-t] + T + S[i:]
                S = S.replace('?', 'a')
                print(S)
                exit()
    print('UNRESTORABLE')
    exit()

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

int n, k, l, t;

int main(){
    vector<int> s;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> l;
        s.push_back(l);
    }

    sort(s.begin(), s.end());

    for(int i = n-k; i < n; i++){
        t = t + s[i];
    }

    cout << t;


}

//g++ -std=c++14 comp.cpp; ./a.exe


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n; cin >> n;
	vector<pair<int,int> > e;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		e.push_back({x, i + 1});
	}
	sort(e.begin(), e.end());
	for(int i = 0; i < n; i++) cout << e[i].second << " ";
	cout << endl;
	return 0;
}


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

signed main()
{
    int n,m; cin >> n >> m;
    vector<int> h(n+1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    vector<int> a(m+1), b(m+1);
    for (int i = 1; i <= m; ++i)
        cin >> a[i] >> b[i];

    vector<int> good(n+1,1);
//    vector<int>noPath(n+1,1);
    for (int i = 1; i <= m; ++i){
        if (h[a[i]]>h[b[i]]) good[b[i]] = 0;
        if (h[b[i]]>h[a[i]]) good[a[i]] = 0;
        if (h[b[i]]==h[a[i]]) good[b[i]] = good[a[i]] = 0;
//        noPath[a[i]] = 0;
//        noPath[b[i]] = 0;
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += good[i];
//    for (int i = 1; i <= n; ++i) ans += noPath[i];
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4804
#include <stdio.h>

int main() {
	int N;
	scanf("%d",&N);
	if (N==2) {
		printf("2");
		return 0;
	}
	if (N % 2 == 0) {
		N++;
	}
	for (int i = N;i<2*N; i = i + 2) {
		for (int j = 3; j <= i/2; j = j + 2) {
			if (i % j == 0) {
				goto AC;
			}
		}
		printf("%d",i);
		break;
		AC:printf("");
	}
	return 0;
}

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

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

    map<int64_t, vector<int64_t>> td;
    for (size_t i = 0; i < n; i++) {
        int64_t t, d;
        cin >> t >> d;
        td[t].push_back(d);
    }

    vector<int64_t> m{0}, o{0};
    for (auto& e : td) {
        sort(begin(e.second), end(e.second));
        m.push_back(e.second.back());
        copy(begin(e.second), end(e.second) - 1, back_inserter(o));
    }

    sort(rbegin(m), rend(m) - 1);
    sort(rbegin(o), rend(o) - 1);

    for (int i = 0; i + 1 < m.size(); i++) m[i+1] += m[i];
    for (int i = 0; i + 1 < o.size(); i++) o[i+1] += o[i];

    int64_t ans = 0;
    for (int64_t x = max(1, k - ((int) o.size() - 1)); x <= min(k, (int) m.size() - 1); x++) {
        ans = max(ans, m[x] + o[k - x] + x * x);
    }

    cout << ans << endl;
}


Measured memory_bytes: 12280
#include<bits/stdc++.h>
using namespace std;
string str;
int N;
void connect(int a,int b)   //ou-ou
{
    cout<<a<<" "<<b<<endl;
    cout<<a<<" "<<a+1<<endl;
    cout<<a+1+N<<" "<<b+1<<endl;
    cout<<a+N<<" "<<a+1+N<<endl;
}
int main()
{
    cin>>N;
    int dN=N;
    ios::sync_with_stdio(false);
    while(dN)
    {
        if(dN&1) str="1"+str;
        else str="0"+str;
        dN>>=1;
    }
    int p=0;
    for(int i=1;i<str.size();++i)
        if(str[i]=='1')
            p=i;
    if(N<=2||p==0)
    {
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    cout<<1<<" "<<2<<endl;
    cout<<2<<" "<<3<<endl;
    cout<<3<<" "<<1+N<<endl;
    cout<<1+N<<" "<<2+N<<endl;
    cout<<2+N<<" "<<3+N<<endl;
    int j=1;
    for(int i=4;i<N;i+=2)
    {
        connect(i,1<<j);
        for(int k=0;k<str.size();++k)
        {
            if((1<<k)==i&&str[str.size()-1-k]=='1')
            {
                j=k;
                break;
            }
        }
    }
    if(N%2==0)
    {
        cout<<N<<" "<<(1<<(str.size()-1-p))<<endl;
        cout<<N+N<<" "<<(1<<str.size()-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int dp[n];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++)
    {
        int option=INT_MAX;
        for(int j=1;j<=min(i,k);j++)
            option=min(option,dp[i-j]+abs(a[i]-a[i-j]));
        dp[i]=option;
    }
    cout<<dp[n-1]<<endl;
}


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

using namespace std;
const int N = 100005;
int n, k;
int h[N], sol[N];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> h[i];
	}
	sol[2] = abs(h[1] - h[2]);
	sol[3] = abs(h[1] - h[3]);
	for(int i = 4; i <= n; i ++) {
		sol[i] = min((sol[i - 1] + abs(h[i - 1] - h[i])), sol[i - 2] + abs(h[i - 2] - h[i]));
	}
	cout << sol[n];
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (a).size()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define dump(x) cerr << #x << " = " << (x) << endl;
#define dumpi(i, x) cerr << string((i), ' ') << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
using pii = pair<int, int>;
constexpr int MOD = 1000000007;
constexpr int INF = 1000000000000000;
constexpr double EPS = 1e-10;

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

struct edge {
  int to, cost;
  edge() {}
  edge(int t, int c) : to(t), cost(c) {}
};

int n, m, s, t;
vector<edge> g[2][100010];
int dis[2][100010];

void dijkstra(int k, int start) {
  fill_n((int*)dis[k], 100010, INF);
  dis[k][start] = 0;
  priority_queue<pii, vector<pii>, greater<pii>> que;
  que.emplace(0, start);
  while (!que.empty()) {
    int dd, v;
    tie(dd, v) = que.top(); que.pop();
    if (dd < dis[k][v]) continue;
    for (edge e : g[k][v]) {
      int nv = e.to;
      if (chmin(dis[k][nv], dis[k][v]+e.cost)) {
        que.emplace(dis[k][nv], nv);
      }
    }
  }
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> n >> m >> s >> t;
  s--; t--;
  rep(i, 0, m) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    g[0][u].EB(v, a);
    g[0][v].EB(u, a);
    g[1][u].EB(v, b);
    g[1][v].EB(u, b);
  }
  dijkstra(0, s);
  dijkstra(1, t);
  vector<int> ans;
  int v = n-1;
  for (int i = n-1; i >= 0; i--) {
    int tmp = dis[0][i]+dis[1][i];
    if (tmp < dis[0][v]+dis[1][v]) v = i; 
    ans.EB(INF-(dis[0][v]+dis[1][v]));
  }
  reverse(all(ans));
  rep(i, 0, n) {
    cout << ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 20092
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 2e5 + 7;

vector <int> g[N];

vector <int> l, r;

void dfs(int v, int pr, int c) {
  if (c) {
    l.push_back(v);
  } else {
    r.push_back(v);
  }
  for (int to : g[v]) {
    if (to != pr) {
      dfs(to, v, c ^ 1);
    }
  }
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0, -1, 0);
  vector <int> x, y;
  for (int i= 1; i <= n; i++) {
    if (i % 3 == 1) {
      x.push_back(i);
    } else if (i % 3 == 2) {
      y.push_back(i);
    }
  }
  if (x.size() < y.size()) x.swap(y);
  vector <int> ans(n, -1);
  if (l.size() < r.size()) l.swap(r);
  if (l.size() >= x.size() + y.size()) {
    for (int t : y) x.push_back(t);
    int ptr = 0;
    for (int t : l) {
      if (ptr < (int) x.size()) {
        ans[t] = x[ptr++];
      }
    }
  } else {
    int ptr = 0;
    for (int t : l) {
      if (ptr < (int) x.size()) {
        ans[t] = x[ptr++];
      }
    }
    ptr = 0;
    for (int t : r) {
      if (ptr < (int) y.size()) {
        ans[t] = y[ptr++];
      }
    }
  }
  set <int> q;
  for (int i= 1; i <= n; i++) {
    q.insert(i);
  }
  for (int i = 0; i < n; i++) q.erase(ans[i]);
  for (int i = 0; i < n; i++) {
    if (ans[i] == -1) {
      ans[i] = *q.begin();
      q.erase(q.begin());
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  cout << endl;
}


Measured memory_bytes: 29044
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(0);
#define setnow clock_t tStart;
#define setTime tStart = clock();
#define time0 (double)(clock() - tStart)/CLOCKS_PER_SEC
#define setin(x) ifstream cin(x);
#define setout(x) ofstream cout(x);
#define NMAX 30
typedef long long ll;
typedef long long int lli;
typedef pair < int, int> dbl;
const int maxInt = 1e9*2;
const lli maxLong = 1e18*2;
int main(){
    int n, a, b;
  cin >> n >> a >> b;
  int ans1, ans2;
    cout << min(n * a, b);
  return 0;
}


Measured memory_bytes: 384
//
#include <vector>
#include <set>
#include <map>
#include <array>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <bitset>
//
using ll = long long;
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);++i)
inline void yes(bool cond) { cond ? puts("Yes") : puts("No"); }
template<typename Type> inline void chmin(Type& a, Type b) { if (a > b) a = b; }
template<typename Type> inline void chmax(Type& a, Type b) { if (a < b) a = b; }
template<typename Arr, typename Type> inline void fill(Arr& arr, Type v) { std::fill(arr.begin(), arr.end(), v); }
template<typename Type> inline void sort(Type& arr) { std::sort(arr.begin(), arr.end()); }
template<typename Type> inline Type nth(vector<Type>& arr, size_t pos) { std::nth_element(arr.begin(), arr.begin() + pos, arr.end()); return arr[pos]; }
constexpr double BIGP = 1000000007L;
constexpr double INF_I = std::numeric_limits<double>::max();
constexpr double INF_F = std::numeric_limits<float>::infinity();
constexpr double PI = 3.14159265358979323846L;
//
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;
    ll ans = 0;
    rep(i, 3)
    {
        ans += S[i] == T[i];
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define arr array

using namespace std;

const int e = 2e6 + 69;
const ll mod = 1e9 + 7;

ll a[e];
arr<int, 2>b[e];

//beginner 1999 128



int main()
{
     string s;
     string t;
     cin >> s >> t;
     ll dem = 0;
     for(int i=0; i<s.size(); i++){
        if(s[i] != t[i]) dem ++;
     }
     cout << dem;
}


Measured memory_bytes: 3916
AlmostZERO = 1e-10

def checkOrthogonal(pos)
  ((pos[6] - pos[4]) * (pos[2] - pos[0]) + (pos[7] - pos[5]) * (pos[3] - pos[1])).abs < AlmostZERO
end

while input = $stdin.gets
  if checkOrthogonal(input.chomp.split(" ").map(&:to_f))
    puts "YES"
  else
    puts "NO"
  end
end

Measured memory_bytes: 6112
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i, s, t) for(i = s; i <= t; ++i)

using namespace std;

char s[20];
int n, ans;

int main() {
	scanf("%s", s); n = strlen(s);
	for(int i = 0; i < n; ++i) ans += s[i]-'0';
	for(int i = 0; i < n; ++i)
		ans = max(ans, s[i]-'1'+(n-i-1)*9);
	printf("%d\n", ans);
	return 0;
} 

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

int main() {
	string str[55];
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> str[i];
	}

	int count;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			count = 0;
			if (str[i][j] == '.') {
				for (int k = i - 1; k <= i + 1; k++) {
					for (int l = j - 1; l <= j + 1; l++) {
						if (k < 0 || k >= H) {
							continue;
						}
						if (l < 0 || l >= W) {
							continue;
						}
						if (str[k][l] == '#') {
							count++;
						}
					}
				}
				str[i][j] = char('0' + count);
			}
		}
	}

	for (int i = 0; i < H; i++) {
		cout << str[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#!python3

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


def main():
    d = {N - A[-1]: 1}
    ans = 0
    for i in range(N - 2, -1, -1):
        x = i + 1 + A[i]
        ans += 0 if x not in d else d[x]
        y = i + 1 - A[i]
        if y in d:
            d[y] += 1
        else:
            d[y] = 1
    
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 40412