akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
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;
}
signed main() {
    int A, B, K;
    cin >> A >> B >> K;
    if(A >= K)
        cout << A - K << ' ' << B << endl;
    else if(A + B >= K)
        cout << 0 << ' ' << B - (K - A) << endl;
    else
        cout << 0 << ' ' << 0 << endl;
}


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

typedef long long lint;
typedef pair<int, int> ii;

int MOD = 1e9 + 7;
int INF = 0x3f3f3f3f;
//lint INF = 1e14;

int n;
lint a[200005], ps[200005];

int solve(){
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	partial_sum(a, a+n, ps);
	lint ans = 1e18;
	for(int i=0;i+1<n;i++){
		lint lo = ps[i];
		lint hi = ps[n-1] - ps[i];
		ans = min(ans, abs(lo - hi));
	}
	cout << ans << endl;
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	// int t; cin >> t; while(t--)
	solve();
	// cout << (solve() ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 3328
# include <bits/stdc++.h>
#define INF 9223372036854775807
using namespace std;

int main(){

  int N, M;
  cin >> N >> M;
  array<long int, 2> A[N];
  for(int i=0; i<N; i++){
    cin >> A[i][0] >> A[i][1];
  }
  sort(A, A+N);
  // for(int i=0; i<N;i++){
  //   cout << A[i][0] << endl;
  // }
  int i = 0;
  long int ans = 0;
  while(M > 0 && i < N){
    if(M <= A[i][1]){
      ans += M * A[i][0];
      break;
    } else{
      ans += A[i][1] * A[i][0];
      M -= A[i][1];
      i++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 1792
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const A = parseInt(arg[0]);
    const B = parseInt(arg[1]);
    
    if(A !== 1 && B !== 1) {
        console.log(1)
    }
    
    if(A !== 2 && B !== 2) {
        console.log(2)
    }
    
    if(A !== 3 && B !== 3) {
        console.log(3)
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 22076
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        string S = ReadLine();
        int maxleng = 0;
        for (int i = S.Length - 1; i >= 0; i--)
        {
            if (i % 2 != 0) continue;
            string S1 = S.Substring(0, i / 2);
            string S2 = S.Substring(i / 2,i/2);
            if (S1 == S2)
            {
                WriteLine(i);
                return;
            }
        }
    }
}


Measured memory_bytes: 25968
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define el '\n'
#define MOD 1000000007
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    char k;
    cin >> k;
    switch(k){
        case 'A':
            cout << 'T' << el;
            break;
        case 'T':
            cout << 'A' << el;
            break;
        case 'G':
            cout << 'C' << el;
            break;
        case 'C':
            cout << 'G' << el;
            break;
    }
 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,S,s;
    cin>>N;
    for(int i=1;;i++)
    {
      S=1000*i;
      if(S>N)
      {
          s=S-N;
          break;
      }
      else if(S==N)
      {
          s=0;
         break;
      }
      }
      cout<<s<<endl;
    }


Measured memory_bytes: 3652
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


N, Q = map(int, input().split())
 
class Node():
    def __init__(self):
        self.connected = []
        self.count = 0
 
 
 
def add_count(v, p):
    for c in G[v].connected:
        if c == p:
            continue
        G[c].count += G[v].count
        add_count(c, v)

def add_count2():
    s = [(0, -1)]
    while s:
        v, p = s.pop()
        for c in G[v].connected:
            if c == p:
                continue
            G[c].count += G[v].count
            s.append((c, v))

G = [Node() for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].connected.append(b-1)
    G[b-1].connected.append(a-1)

for _ in range(Q):
    p, x = map(int, input().split())
    G[p-1].count += x

# add_count(0, -1)
add_count2()
counts = [node.count for node in G]
print(*counts)



Measured memory_bytes: 124140
#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 100009;
int k,tot[19];
ll a[maxn][19];
int main(){
    scanf("%d",&k);
    for(int i = 1; i <= 9; i++) a[i][1] = i;
    tot[1] = 9;
    int cnt = 9;
    for(int p = 2; p <= 11; p++)
        for(int i = 1; i <= tot[p-1] && cnt <= k; i++){
            ll ai = a[i][p-1], tmp = ai % 10;
            if(tmp == 0){
                a[++tot[p]][p] = ai * 10;
                a[++tot[p]][p] = ai * 10 + 1;
                cnt += 2;
            }
            else if(tmp == 9){
                a[++tot[p]][p] = ai * 10 + tmp - 1;
                a[++tot[p]][p] = ai * 10 + tmp;
                cnt += 2;
            }
            else{
                a[++tot[p]][p] = ai * 10 + tmp - 1;
                a[++tot[p]][p] = ai * 10 + tmp;
                a[++tot[p]][p] = ai * 10 + tmp + 1;
                cnt += 3;
            }
        }
    cnt = 1;
    for(int p = 1; p <= 11; p++)
        for(int i = 1; i <= tot[p] && cnt <= k; i++,cnt++)
            if(cnt == k)printf("%lld\n",a[i][p]);
    return 0;
}

Measured memory_bytes: 8448
N = int(input())
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
ans = 0
for i in range(N):
    t = 0
    for j in range(0, min(N, i + 1)):
        t += A1[j]
    for k in range(i, N):
        t += A2[k]
    ans = max(t, ans)
print(ans)


Measured memory_bytes: 9084
#include <stdio.h>

int main()
{
  int a, b, c, max;
  scanf("%d %d %d", &a, &b, &c);

  if(a>=b && a>=c) {
    printf("%d\n", a*10+b+c);
  } else if(b>=c && b>=a) {
    printf("%d\n", b*10+a+c);
  } else {
    printf("%d\n", c*10+a+b);
  }    
  
}


Measured memory_bytes: 128
# D - Digits Parade

# dp[i][j] Sの大きい位からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート
# 大きい位から順に始めないと13で割ったときの余りを求める計算量が大きくなる

S = input()

MOD = 10**9 + 7
dp = [[0]*13 for _ in range(len(S))]

if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, len(S)):
    if S[i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for front_number in range(13):
                dp[i][(10 * front_number + q_number) % 13] += dp[i-1][front_number]
                dp[i][(10 * front_number + q_number) % 13] %= MOD
    else:
        for front_number in range(13):
            dp[i][(10 * front_number + int(S[i])) % 13] += dp[i-1][front_number]
            dp[i][(10 * front_number + int(S[i])) % 13] %= MOD

print(dp[len(S)-1][5] % MOD)

Measured memory_bytes: 61916
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b-1);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;cin>>s;
  reverse(all(s));
  ll l=s.length();
  vector<ll>dp(3,1e18),tdp(3,1e18);
  dp[0]=0;
  rep(i,l){
    tdp.assign(3,1e18);
    rep(kuri,3){
      ll wa=kuri+s[i]-'0';
      if(wa%10==0){
        chmin(tdp[wa/10],dp[kuri]);
      }
      else{
        chmin(tdp[wa/10],dp[kuri]+wa%10);
        chmin(tdp[wa/10+1],dp[kuri]+10-wa%10);
      }
    }
    dp=tdp;
  }
  cout<<min({dp[0],dp[1]+1,dp[2]})<<endl;

  return 0;

}


Measured memory_bytes: 1948
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
struct node {
	int x,y;
	friend node operator + (node t1,node t2) { return (node){t1.x+t2.x,t1.y+t2.y}; }
} A,B,C,D,delta;
int main() {

	read(A.x),read(A.y),read(B.x),read(B.y);
	delta.x=A.y-B.y;
	delta.y=B.x-A.x;
	C=B+delta,D=A+delta;
	printf("%d %d %d %d\n",C.x,C.y,D.x,D.y);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int fr = 0;
		int ba = 0;
		int ans = 0;
		int[] list = new int[N + 1];
		for(int i = 1; i < N + 1; i++) {
			list[i] = sc.nextInt();
			fr += list[i];
		}
		ans = fr;
		for(int i = 1; i < N + 1; i++) {
			fr -= list[i];
			ba += list[i];
			ans = Math.min(ans, Math.abs(fr - ba));
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 23252
#include <iostream>
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

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

  ll n; cin >> n;

  ll ans;
  for(int i = 1; i*i <= n; ++i) {
    ans = i*i;
  }
  cout << ans << '\n';
  return 0;
}


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

signed main(){
    ll n;
    cin>>n;
    ll ans = n;
    for(int i=1;i<n;i++){
        ans += (i+1)*(n-i);
        ll a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        ans -= a*(n-b+1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
class Range {
    using T = long long;
    class Iterator {
        T val, step, diff;
    public:
        Iterator(T v, T s, T d): val(v), step(s), diff(d) {}
        T operator*() { return val + diff; }
        bool operator!=(const Iterator &itr) { return step > 0 ? val < itr.val : val > itr.val; }
        Iterator operator++() { val += step; return *this; }
    };
    Iterator _begin, _end;
public:
    Range(T b, T e, T s, T d): _begin(b, s, d), _end(e, s, d) {
        if (s < 0) { _begin = Iterator(e - 1, s, d); _end = Iterator(b - 1, s, d); }
    }
    Range(T b, T e, T s): Range(b, e, s, 0) {}
    Range(T b, T e): Range(b, e, 1, 0) {}
    Range(T e): Range(0, e, 1, 0) {}
    Iterator begin() { return _begin; }
    Iterator end() { return _end; }
};
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, k;
    cin, n, k;
    vector<int> a(n);
    for (auto &aa : a) {
        cin, aa;
        aa--;
    }
    int pos = 0;
    while (k) {
        if (k & 1) {
            pos = a[pos];
        }
        vector<int> nxt(n);
        for (ll i : Range(n)) {
            nxt[i] = a[a[i]];
        }
        a = nxt;
        k >>= 1;
    }
    print(pos + 1);
    return 0;
}


Measured memory_bytes: 4784
#include <bits/stdc++.h>
using namespace std;
const int N=2*1e5+1;
string s;
int i,p[26][N],c[26],odd,f[N],n,FT[N];
int find(int i){return i?FT[i]+find(i-(i&-i)):0;}
void add(int i){while(i<=n)FT[i]++,i+=i&-i;}
int main(){
	cin>>s;n=s.size();
	for(i=0;s[i];i++)
		p[s[i]-'a'][c[s[i]-'a']++]=i;
	for(i=0;i<26;i++)if(c[i]&1)odd++;
	if(odd>1)return puts("-1"),0;
	for(i=0;i<26;i++)
		for(int j=0;j<c[i];j++)
			f[p[i][c[i]-1-j]]=p[i][j]+1;
	long long ans=0;
	for(int i=n-1;~i;i--){
		//cout<<ans<<endl;
		ans+=(n-1-i)-
		find(f[i]);
		//cout<<ans<<endl<<endl;
		add(f[i]);
	//	cout<<3<<endl;
	}
//	cout<<3<<endl;
	cout<<ans/2<<endl;
}


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

int main(void) {
	int n;
	cin >> n;
	vector<int> v(n);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	sort(v.begin(), v.end());
	double ans = v[0];
	for (int i = 1; i < n; i++) {
		ans = (ans + v[i]) / 2;
	}
	printf("%.10f\n", ans);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		int L = sc.nextInt();
		double l = L / 3.0;
		System.out.printf("%f\n", l * l * l);
	}
}

class Main {
	public static void main(String... args) {
		Scanner in = new Scanner(System.in);

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

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

#define loop(n) for(int i = 0;i < (int)(n);++i)
#define rep(i,n) for(int i = 0;i < (int)(n);++i)
#define all(vec) (vec).begin(),(vec).end()
#define Sort(vec) sort(all(vec))
#define Rev(vec) reverse(all(vec))

using Graph = vector<vector<int>>;

namespace Input
{
                
    void input(){return;}
    template<typename First,typename... Rest> void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}
    
    void inputVec(){return;}
    template<typename First,typename... Rest> void inputVec(vector<First> &first,Rest&... rest){
        int N = first.size();
        for(int i = 0;i < N;i++){
            cin >> first[i];
        }
        inputVec(rest...);
    }
    
    template<typename First,typename Second> void inputTwoVec(vector<First> &first,vector<Second>& second){
        int N = first.size();
        for(int i = 0;i < N;i++){
            cin >> first[i] >> second[i];
        }
    }

    void inputGraph(Graph &g,int path_num,bool isdirected){
        for(int i = 0;i < path_num;i++){
            int a,b;
            cin >> a >> b;
            a--;b--;
            if(isdirected){
                g[a].push_back(b);
            }
            else{
                g[a].push_back(b);
                g[b].push_back(a);
            }
        }
    }
}

long long pow5(long long n){
    return n * n * n * n * n;
}

void calculate(){
    long long X;
    Input::input(X);
    for(long long i = -1000;i <= 1000;i++){
        for(long long j = -1000;j <= 1000;j++){
            if(pow5(i) - pow5(j) == X){
                cout << i << " " <<  j << '\n';
                return;
            }
        }
    }
}

int main(int,char**){
    calculate();    
}




Measured memory_bytes: 3640
n,k = map(int,input().split())
array = []
for i in range(n):
  array.append(int(input()))
  
array.sort()

min = 1000000000
for i in range(n-k+1):
  dif = array[i+k-1] - array[i]
  if min>dif:
    min = dif
    
print(min)


Measured memory_bytes: 7384
if __name__ == '__main__':
    x = int(input())
    a = -1
    b = -1
    for i in range(0,1001,1):
        got = False
        for j in range(0,1001,1):
            # print(str(i)+" "+str(j))
            if (i**5 - j**5) == x:
                a = i
                b = j
                got = True
                break
            if (i**5 + j**5) == x:
                a = i
                b = -1*j
                got = True
                break
        if got:
            break
    print(*[a,b])



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

void main_()
{
    ll N;
    cin >> N;
    map<ll, ll> As_map;
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        As_map[a]++;
    }

    ll even = 0;
    for (auto&& a : As_map) {
        if (a.second % 2 == 0) {
            even++;
        }
    }
    ll ans = As_map.size() - ((even % 2 != 0) ? 1 : 0);
    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 6528
#include<iostream>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 10010
using namespace std;

int par[MAX];

int find(int x)
{
  if(x == par[x])return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y)
{
  x = find(x), y = find(y);
  if(x != y)par[x] = y;
  find(x),find(y);
}

int main()
{
  int n,q,com,x,y;
  cin >> n >> q;
  rep(i,n)par[i] = i;
  rep(i,q)
    {
      cin >> com >> x >> y;
      if(com == 0)unit(x,y);
      else cout << (find(x)==find(y)?1:0) << endl;
    }

  return 0;
}

Measured memory_bytes: 1320
from collections import Counter
n = int(input())
D = list(map(int,input().split()))
D = Counter(D)
m = int(input())
T = list(map(int,input().split()))
T = Counter(T)
#print(D)
#print(T)
for key in T:
    if D[key] < T[key]:
        print('NO')
        exit()

print('YES')

Measured memory_bytes: 122960
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val p = (0 until n).map { sc.next().toLong() }
    println(problem153d(n, k, p))
}

fun problem153d(n: Int, k: Int, p: List<Long>): Double {
    fun sum(n: Long): Long {
        var sum = 0L
        for (i in 1..n) {
            sum += i
        }
        return sum
    }
    val list = DoubleArray(n + 1) { 0.0 }
    for (i in 0 until n) {
        val pi = p[i]
        list[i + 1] = list[i] + sum(pi) / pi.toDouble()
    }
    var res = 0.0
    for (i in 0..n - k) {
        val v = list[k + i] - list[i]
        if (res < v) res = v
    }
    return res
}

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

int b[2010][2010];
int g[2010][2010];
int root[2010][2010];
int r[2010][2010];
int l[2010][2010];
int u[2010][2010];
int d[2010][2010];

int H, W, Q;

bool in(int x, int y) {
	return 0 <= x && x < W && 0 <= y && y < H;
}

struct P {
	int x, y;
};


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

	cin >> H >> W >> Q;
	for(int i = 0; i < H; i++) {
		string s;
		cin >> s;
		for(int j = 0; j < W; j++) {
			b[i][j] = s[j] == '1';
		}
	}

	memset(g, -1, sizeof g);
	int group = 0;
	for(int y = 0; y < H; y++) {
		for(int x = 0; x < W; x++) {
			if(b[y][x] == 0 || g[y][x] != -1) continue;
			root[y][x] = 1;
			g[y][x] = group;
			queue<P> q;
			q.push({ x, y });
			while(q.size()) {
				int X = q.front().x, Y = q.front().y;
				q.pop();
				int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
				for(int k = 0; k < 4; k++) {
					int NX = X + dx[k], NY = Y + dy[k];
					if(!in(NX, NY) || b[NY][NX] == 0 || g[NY][NX] != -1) continue;
					g[NY][NX] = group;
					if(k == 0) r[Y][X] = 1;
					if(k == 1) d[Y][X] = 1;
					if(k == 2) l[Y][X] = 1;
					if(k == 3) u[Y][X] = 1;
					q.push({ NX, NY });
				}
			}
			group++;
		}
	}

	for(int j = 0; j < W; j++) {
		int sr = 0, sl = 0;
		for(int i = 0; i < H; i++) {
			sr += r[i][j];
			r[i][j] = sr;
			sl += l[i][j];
			l[i][j] = sl;
		}
	}
	for(int i = 0; i < H; i++) {
		int su = 0, sd = 0;
		for(int j = 0; j < W; j++) {
			su += u[i][j];
			u[i][j] = su;
			sd += d[i][j];
			d[i][j] = sd;
		}
	}

	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			root[i + 1][j] += root[i][j];
		}
	}
	for(int j = 0; j < W; j++) {
		for(int i = 0; i < H; i++) {
			root[i][j + 1] += root[i][j];
		}
	}

	while(Q--) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		x1--, y1--, x2--, y2--;
		int rootsum = root[y2][x2];
		if(y1 - 1 >= 0) rootsum -= root[y1 - 1][x2];
		if(x1 - 1 >= 0) rootsum -= root[y2][x1 - 1];
		if(x1 - 1 >= 0 && y1 - 1 >= 0) rootsum += root[y1 - 1][x1 - 1];

		int rsum = 0, lsum = 0, usum = 0, dsum = 0;
		if(x1 - 1 >= 0) {
			rsum = r[y2][x1 - 1];
			if(y1 - 1 >= 0) rsum -= r[y1 - 1][x1 - 1];
		}
		if(x2 + 1 < W) {
			lsum = l[y2][x2 + 1];
			if(y1 - 1 >= 0) lsum -= l[y1 - 1][x2 + 1];
		}
		if(y1 - 1 >= 0) {
			dsum = d[y1 - 1][x2];
			if(x1 - 1 >= 0) dsum -= d[y1 - 1][x1 - 1];
		}
		if(y2 + 1 < H) {
			usum = u[y2 + 1][x2];
			if(x1 - 1 >= 0) usum -= u[y2 + 1][x1 - 1];
		}
		cout << rootsum + rsum + lsum + dsum + usum << endl;
	}
}

Measured memory_bytes: 112256
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1e6+5;
int q,t,f;
char c,s[maxn];
typedef pair<int, int>pii;
const long long mod=1e9+7;
int main(){
	scanf("%s",s+300000);
	int beg=300000,flg=1;
	int end=strlen(s+beg)+beg;
	cin>>q;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			flg=(3-flg);
		}
		else{
			cin>>f>>c;
			if(flg==1){
				if(f==1){
					s[beg-1]=c;
					beg--;
				}
				else{
					s[end++]=c;
				}	
			}
			else{
				if(f==2){
					s[beg-1]=c;
					beg--;
				}
				else{
					s[end++]=c;
				}
			}
		}
	}
	if(flg==1){
		for(int i=beg;i<end;i++){
			printf("%c",s[i]);
		} 
	}
	else{
		for(int i=end-1;i>=beg;i--){
			printf("%c",s[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 896
A = int(input())
B = int(input())
C = int(input())
X = int(input())

wayCount = 0

for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            sum = 500 * a + 100 * b + 50 * c
            if sum == X:
                wayCount += 1
            
print(wayCount)

Measured memory_bytes: 9176
import Control.Applicative ((<$>))
import Control.Monad (replicateM, unless, when, guard, foldM)
import Data.Vector.Unboxed (Vector, (!), (//))
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed.Mutable (IOVector, STVector)
import qualified Data.Vector.Unboxed.Mutable as VM
import Control.Monad.ST

main :: IO ()
main = do
  [w, h] <- map read <$> words <$> getLine
  unless (w == 0 && h == 0) $ do
    solve w h <$> V.fromList <$> concat <$> replicateM h (map read <$> words <$> getLine) >>= print
    main

solve :: Int -> Int -> Vector Int -> Int
solve w h v = runST $ do
  mp <- V.thaw v
  foldM (f mp) 0 [(i, j) | i <- [0 .. w-1], j <- [0 .. h-1]]
  where toIx (i, j) = i + w * j
        f mp ct (i, j) = do
          x <- VM.read mp (toIx (i, j))
          if x == 0 then return ct
            else do
            clear mp (i, j)
            return $ ct + 1
        clear mp (i, j) = do
          x <- VM.read mp (toIx (i, j))
          when (x == 1) $ do
            VM.write mp (toIx (i, j)) 0
            mapM_ (clear mp) $ do
              (i', j') <- [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i-1,j-1),(i+1,j-1),(i-1,j+1),(i+1,j+1)]
              guard $ i' >= 0 && j' >= 0 && i' < w && j' < h
              return (i', j')



Measured memory_bytes: 9324
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define vii vector <int>
#define vll vector <long long>
#define pii pair <int, int>
#define repDown(i,a,n) for(int i=n;i>a;i--)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define endl '\n'
#define mem(a,b) memset(a, b, sizeof a)
#define max(a,b,c) max(c, min(a,b))
#define min(a,b,c) min(c, min(a,b))
ll mod=1000000007;
using namespace std;
void print(vector <int> &arr){
	for(int i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	
	cout<<endl;
}
void printll(vector <ll> &arr){
	for(int i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	
	cout<<endl;
}

int main(){
/////////////////////////////////////////////////////////////////////
//	ios_base::sync_with_stdio(false);
//	cin.tie(nullptr);
//	cout.tie(nullptr);
//	cerr.tie(nullptr);
//For fast IO
///////////////////////////////////////////////////////////////////// 

	ll n, a, b;
	cin>>n>>a>>b;
	ll bballs=(n/(a+b))*a, coeff=n%(a+b);
	if(coeff>a) bballs+=a;
	else bballs+=coeff;
	cout<<bballs<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)
#define rrep(i, j, n) for (int i = (int)n - 1; j <= i; --i)

#define dbg(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
template <typename T>
ostream& operator<<(ostream& os, vector<T>& a) {
  for (int i = 0; i < (int)a.size(); ++i)
    os << a[i] << " \n"[i == (int)a.size() - 1];
  return os;
}

constexpr ll MOD = 1000000007;
constexpr int INF = 0x3f3f3f3f;
constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL;

int main() {
  ll k;
  cin >> k;

  ll now = 0;
  ll ten = 1;
  rep(i, 0, k + 5) {
    now = (now + ten * 7 % k) % k;
    if (now == 0) {
      cout << i + 1;
      return 0;
    }
    ten = ten * 10 % k;
  }
  cout << "-1";
  return 0;
}


Measured memory_bytes: 3636
from __future__ import print_function
while(1):
    x = raw_input()
    if(x == "0 0"):
        break
    x = x.split(" ")
    h = int(x[0])
    w = int(x[1])
    for j in range(0,w):
        print("#", end="")
    print("\n",end="")
    for i in range(0,h-2):
        print("#",end="")
        for k in range(0,w-2):
            print(".", end="")
        print("#")
    for l in range(0,w):
        print("#", end="")
    print("\n",end="")
    print("\n",end="")


Measured memory_bytes: 4684
//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define repe(i, a, b) for (int i = (a); i <= (b); i++)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define mst(a, b)   memset((a), (b), sizeof(a))
#define gc() gutchar()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pr;
typedef long long ll;
const double eps = 1e-5;
const int inf = 0x3f3f3f3f;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const ll mod = 1e9+7;
const int N = 2e5+5;
 
int main()
{
	int n, m;
	cin >> n >> m;
	if (m >= n)	puts("Yes");
	else	puts("No");
	return 0;
}

Measured memory_bytes: 256
// abc089_b
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(int argc, char *argv[])
{
  int n;
  char s;
  cin>>n;
  rep(i,n){
    cin>>s;
    if(s=='Y'){
      cout<<"Four"<<endl;
      return 0;
    }
  }
  cout<<"Three"<<endl;
  return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
H=[]
for i in range(n):
    H.append(int(input()))
 
H.sort()
 
#print(H)
 
ans=H[n-1]-H[0]
 
for i in range(n-k+1):
    #print(H[i+k-1]-H[i])
    ans=min(ans,H[i+k-1]-H[i])
 
print(ans)

Measured memory_bytes: 7384
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 'P', 'Q', 'R' ツづー '1', '2', '3' ツづ可置ツつォツ環キツつヲツづゥ
void PQR_change(string& s ,char p , char q , char r ){
	for(int i=0 ; i < s.size() ; i++ ){
		if( s[i] == 'P' ) s[i] = p;
		if( s[i] == 'Q' ) s[i] = q;
		if( s[i] == 'R' ) s[i] = r;
	}
}

// "--"(ツ連ツ堕アツつキツづゥ2ツづつづ個マツイツナツス) ツづー "" ツづ可置ツつォツ環キツつヲツづゥ
void minus_erace(string& s){
	for(int i=1 ; i < s.size() ; i++ ){
		if( s[i] == '-' && s[i-1] == '-' ){
			s.erase( i-1 , 2 );
			i = 0;
		}
	}
}

int eval(string s, int& pos){
	if( s[pos] == '0' ){ pos++; return 0; }
	if( s[pos] == '1' ){ pos++; return 1; }
	if( s[pos] == '2' ){ pos++; return 2; }
	if( s[pos] == '-' ){ pos++; return 2 - eval(s,pos) ; }
	if (s[pos] == '(') { 
		++pos; 
		int a = eval(s, pos);
		char c = s[pos++];
		int b = eval(s, pos);
		++pos;
		if( c == '*' ){
			return (a * b + 1) / 2;
		}else if( c == '+' ){
			return max(a, b);
		}
	}
}

int main(){
	string s;
	while( cin >> s , s != "." ){
		int ans = 0;
		for(char p = '0' ; p <= '2' ; p++ ){
			for(char q = '0' ; q <= '2' ; q++ ){
				for(char r = '0' ; r <= '2' ; r++ ){
					string ex = s;
					// 'P', 'Q', 'R' ツづー '1', '2', '3'ツづ可置ツつォツ環キツつヲツづゥ
					PQR_change( ex , p , q , r );
					// "--"(ツ連ツ堕アツつキツづゥ2ツづつづ個マツイツナツス) ツづー ""ツづ可置ツつォツ環キツつヲツづゥ
					minus_erace( ex );
					
					// ツ篠ョツづ個評ツ可ソ
					int t=0;
					int val = eval( ex , t );
					if( val == 2 ){
						ans++;
					}
				}
			}
		}
		cout << ans << endl;
	}	
}

Measured memory_bytes: 0
//
//  main2.cpp
//  dp
//
//  Created by 贾皓翔 on 2020/1/14.
//  Copyright © 2020 贾皓翔. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int N,M,i;
    int ac[100005];
    int wa[100005];

    scanf("%d%d",&N,&M);
    for(i=1; i<=N; i++)
    {
        ac[i]=0;
        wa[i]=0;
    }
    int p;
    char S[3];
    if(M==0)
    {
        printf("0 0");
    }
    else
    {
        int acnum=0,wanum=0;
        for(i=1; i<=M; i++)
        {
            scanf("%d%s",&p,S);
            if(ac[p]==0)
            {
               
                if(!strcmp(S,"WA"))
                {
                    wa[p]++;

                }
                else if(!strcmp(S,"AC"))
                {
                    ac[p]=1;
                    acnum++;
                }
            }
        }
        for(i=1; i<=N; i++)
        {
            if (ac[i]) {
                wanum+=wa[i];
            }
        }
        printf("%d %d",acnum,wanum);

    }
    return 0;

}


Measured memory_bytes: 896
import sys

def main():

    # sys.stdin = open('input153d.txt')

    h = int(input()
            )
    print(func(h) - 1)

def func(h):
    
    if h < 1:
        return 1
    else:
        return 2 * func(h // 2) 


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define inf LLONG_MAX
#define bp __builtin_popcountll
#define pb push_back
#define ff first
#define ss second
#define P pair<ll,ll>
#define N 100001
#define all(a) a.begin(),a.end()
#define LG 20
#define int ll
#define vi vector<int>
#define mod 1000000007
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ps(x,y)

int sum(int n){
    return (n*(n+1))/2;
}

int solve(int k,int n){
    k--;
    int ans;
    ans=sum(n) - sum(n-k-1) - sum(k) + 1;
    return ans%mod;
//    return ans;
}


signed main(){
    int n,k;
    cin>>n>>k;
    int ans=0;
    for(int i=k;i<=n+1;i++){
//        cout<<ans<<endl;
        ans+=solve(i,n);
        ans=ans%mod;
    }
    cout<<ans%mod;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n,k;
    cin >> n >> k;
    int l[n];
    REP(i,n) cin >> l[i];
    sort(l, l + n);
    reverse(l, l + n);
    int ans = 0;
    REP(i,k) ans += l[i];
    cout << ans << endl;
}

Measured memory_bytes: 256
a, b, c, k = map(int, input().split())
res = 0
if k == a:
    print(a)
elif k < a:
    print(k)
else:
    res += a
    k -= a
    if k > b:
        k -= b
        if k > c or k == c:
            res -= c
            print(res)
        else:
            res-= k
            print(res)
    else:
        print(res)

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin>>n;
	vi d(n);
	rep(i, n) cin>>d[i];

	ll ans=0;
	rep(i, n)rep(j, n){
		if (i!=j){
			ans += d[i]*d[j];
		}
	}
	cout << ans/2 << "\n";
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
x_y = []
x = []
y = []
for i in range(n):
    a,b = map(int, input().split())
    x.append(a)
    y.append(b)
    x_y.append([a,b])
ans = 10**19
def check(a,b,c,d):
    count = 0
    for i in range(n):
        s,t = x_y[i]
        if a <= s <= b and c <= t <= d:
            count += 1
    if count >= k:
        return True
    else:
        return False
x.sort()
y.sort()
for x_1 in range(n):
    for x_2 in range(x_1+1,n):
        for y_1 in range(n):
            for y_2 in range(y_1+1,n):
                if check(x[x_1],x[x_2],y[y_1],y[y_2]):
                    rect_area = (x[x_2] - x[x_1]) * (y[y_2] - y[y_1])
                    ans = min(ans, rect_area)
print(ans)


Measured memory_bytes: 58716
n,x,m=map(int,input().split())
ans=x
count=1
table=[0]*m
table[x]=1
r=[0,x] #一般項
f=1
for i in range(n-1):
    x=pow(x,2,m)
    ans+=x
    count+=1
    if table[x]:
        f=0
        break
    r.append(x)
    table[x]=count
if f or table[0]:
    print(ans)
    exit()
ans=0
'''
table[x]項目とcount項目が同じ
loop前の項+loopの項*loop数+足りない分
'''
ans=sum(r[:table[x]])
loop=(n-table[x]+1)//(count-table[x])
ans+=sum(r[table[x]:])*loop
nokori=(n-table[x]+1)%(count-table[x])
for i in range(nokori):
    ans+=r[table[x]+i]
print(ans)

Measured memory_bytes: 70016
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int s[6];
    int i,j;
    int answer[25];
    int tmp;
    int count=0;
    int top,front;
    for(i=0;i<6;i++){
        scanf("%d",&s[i]);
    }
    scanf("%d",&j);
    for(i=0;i<j;i++){
        scanf("%d",&top);
        scanf("%d",&front);
        if(top==s[0]){
            if(front==s[1]){
                printf("%d\n",s[2]);
            }if(front==s[2]){
                printf("%d\n",s[4]);
            }if(front==s[3]){
                printf("%d\n",s[1]);
            }if(front==s[4]){
                printf("%d\n",s[3]);
                
            }
        }else if(top==s[1]){
            if(front==s[0]){
                printf("%d\n",s[3]);
            }if(front==s[2]){
                printf("%d\n",s[0]);
            }if(front==s[3]){
                printf("%d\n",s[5]);
            }if(front==s[5]){
                printf("%d\n",s[2]);
            }
        }else if(top==s[2]){
            if(front==s[0]){
                printf("%d\n",s[1]);
            }if(front==s[1]){
                printf("%d\n",s[5]);
            }if(front==s[4]){
                printf("%d\n",s[0]);
            }if(front==s[5]){
                printf("%d\n",s[4]);
            }
        }else if(top==s[3]){
            if(front==s[0]){
                printf("%d\n",s[4]);
            }if(front==s[1]){
                printf("%d\n",s[0]);
            }if(front==s[4]){
                printf("%d\n",s[5]);
            }if(front==s[5]){
                printf("%d\n",s[1]);
            }
        }else if(top==s[4]){
            if(front==s[0]){
                printf("%d\n",s[2]);
            }if(front==s[2]){
                printf("%d\n",s[5]);
            }if(front==s[3]){
                printf("%d\n",s[0]);
            }if(front==s[5]){
                printf("%d\n",s[3]);
            }

        }else if(top==s[5]){
            if(front==s[1]){
                printf("%d\n",s[3]);
            }if(front==s[2]){
                printf("%d\n",s[1]);
            }if(front==s[3]){
                printf("%d\n",s[4]);
            }if(front==s[4]){
                printf("%d\n",s[2]);
            }

        }
        
        
    }
    
    
    return 0;
}

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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define OUT(a) cout << (a) << endl;
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);

template <class T, class S>
using umap = std::unordered_map<T, S>;
using ll = long long;
using namespace std;

int main() {
    ll s, w;

    cin >> s >> w;

    if (s <= w){
        cout << "unsafe" <<endl;
    } else {
        cout << "safe" << endl;
    }

    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define pb(x) push_back(x);

using namespace std;

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

	vector<int> v;
	int prev = -1,cnt = 0,m_e = -1, first = -1;
	
	for(int i = 0; i < n; i++){
		int in;
		cin >> in;
		if(prev == -1){first = in;prev = in;continue;}
		m_e = max(m_e,in - prev);
		cnt += in - prev;
		prev = in;
	}
	cnt += all - prev + first;
	m_e = max(m_e,all-prev + first);
	cout << cnt - m_e;	
}

Measured memory_bytes: 256
N, K = map(int, input().split())
S = list(input())

hikkuri = 0

for i in range(len(S) - 1):
    if S[i] != S[i + 1]:
        hikkuri += 1

shiawase = len(S) - hikkuri - 1

for i in range(K):
    if hikkuri >= 2:
        shiawase += 2
        hikkuri -= 2
    elif hikkuri == 1:
        shiawase += 1
        break

print(shiawase)

Measured memory_bytes: 4084
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 4
#define U 16
#define LIM 100


int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
char dir[4]={'r','u','l','d'};
int m[U][U];


typedef struct {
  int a[U],s,md;
}P;

P st;
int lim,p[LIM];

int get(P);
int solved();
int dfs(int,int);
int intedeep(P);
int max(int,int);
int min(int,int);
void swap(int *,int *);

int main(){
  int i,j;
  P in;
 

  for(i=0;i<U;i++){
    for(j=0;j<U;j++){
      m[i][j]=abs(i/N - j/N) + abs(i%N - j%N);
    }
  }
  for(i=0;i<U;i++){
    scanf("%d",&in.a[i]);
    
    if(in.a[i]==0){
      in.a[i]=U;
      in.s = i;
    }
  }
  
  printf("%d\n",intedeep(in));

  return 0;
}

int get(P x){
  int sm=0,i;

  for(i=0;i<U;i++){
    if(x.a[i]==U) continue;

    sm+=m[i][x.a[i]-1];
		  
  }
  return sm;
}

int solved(){
  int i;

  for(i=0;i<U;i++)
    if(st.a[i] != i+1) return 0;
  return 1;

}

int intedeep(P in){
  int i,a;

  in.md = get(in);
  for(lim=in.md;lim<=LIM;lim++){
    st=in;
    if(dfs(0,-LIM)){
      a=0;
      for(i=0;i<lim;i++){
	a++;
      }return a;
    
    
    }
  }
  return -1;
}

int dfs(int dep,int pre){
  int x1,y1,x2,y2,i;
  x1= st.s/N;
  y1= st.s%N;
  P temp;
  if(st.md == 0) return 1;
  if(dep + st.md>lim) return 0;
  for(i=0;i<4;i++){
    x2 = x1 + dx[i];
    y2 = y1 + dy[i];
    if(x2<0||x2>=N||y2<0||y2>=N) continue;
    if(max(pre,i)-min(pre,i)==2) continue;
    temp = st;
    st.md-=m[x2*N +y2][st.a[x2*N +y2]-1];
    st.md+=m[x1*N +y1][st.a[x2*N +y2]-1];
    swap(&st.a[x2*N+y2],&st.a[x1*N+y1]);
    st.s=x2*N+y2;
    if(dfs(dep+1,i)){
      p[dep] = i;
      return 1;
    }
    st=temp;
  }
  return 0;
}

int max(int pre,int i){
  if(pre>i) return pre;
  else return i;
}

int min(int pre,int i){
  if(pre<i) return pre;
  else return i;
}

void  swap(int *x,int *y){

  int temp;

  temp = *x;
  *x = *y;
  *y = temp;

}



Measured memory_bytes: 2104
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from bisect import bisect_left,bisect_right

class MinCostFlow:
    def __init__(self,n):
        self.n=n
        self.edges=[[] for i in range(n)]
    def add_edge(self,fr,to,cap,cost):
        self.edges[fr].append([to,cap,cost,len(self.edges[to])])
        self.edges[to].append([fr,0,-cost,len(self.edges[fr])-1])
    def MinCost(self,source,sink,flow):
        inf=10**15+1
        n=self.n; E=self.edges
        mincost=0
        prev_v=[0]*n; prev_e=[0]*n
        while flow:
            dist=[inf]*n
            dist[source]=0
            q=deque([source])
            Flag=[False]*n
            Flag[source]=True
            while q:
                v=q.popleft()
                if not Flag[v]:
                    continue
                Flag[v]=False
                for i,(to,cap,cost,_) in enumerate(E[v]):
                    if cap>0 and dist[to]>dist[v]+cost:
                        dist[to]=dist[v]+cost
                        prev_v[to],prev_e[to]=v,i
                        q.append(to)
                        Flag[to]=True
            if dist[sink]==inf:
                return 1
            f,v=flow,sink
            while v!=source:
                f=min(f,E[prev_v[v]][prev_e[v]][1])
                v=prev_v[v]
            flow-=f
            mincost+=f*dist[sink]
            v=sink
            while v!=source:
                E[prev_v[v]][prev_e[v]][1]-=f
                rev=E[prev_v[v]][prev_e[v]][3]
                E[v][rev][1]+=f
                v=prev_v[v]
        return mincost

n=int(input())
J=[]
L_org,D_org=[1]*n,[1]*n
for _ in range(n):
    x,y,v=map(int,input().split())
    J.append((x,y,v))
m=int(input())
T=[]
for _ in range(m):
    t,a,b=input().split()
    a,b=int(a),int(b)
    T.append((t,a,b))
    if t=='L':
        L_org[b]=a+1
    elif t=='D':
        D_org[b]=a+1
for i in range(1,n):
    L_org[i]=max(L_org[i-1],L_org[i])
    D_org[i]=max(D_org[i-1],D_org[i])

def solve(k):
    L,D=L_org[:k],D_org[:k]
    R,U=[100]*k,[100]*k
    for t,a,b in T:
        if k-b-1>=0:
            if t=='R':
                R[k-b-1]=a-1
            elif t=='U':
                U[k-b-1]=a-1
    for i in range(k-2,-1,-1):
        R[i]=min(R[i],R[i+1])
        U[i]=min(U[i],U[i+1])
    solver=MinCostFlow(2*n+2*k+2)
    for i in range(1,k+1):
        solver.add_edge(0,i,1,0)
        solver.add_edge(2*n+k+i,2*n+2*k+1,1,0)
    for i in range(n):
        v=J[i][2]
        solver.add_edge(k+i+1,n+k+i+1,1,-v)
    for i in range(n):
        x,y=J[i][0],J[i][1]
        l=bisect_right(L,x)
        r=bisect_left(R,x)+1
        d=bisect_right(D,y)
        u=bisect_left(U,y)+1
        for j in range(r,l+1):
            solver.add_edge(j,k+i+1,1,0)
        for j in range(u,d+1):
            solver.add_edge(n+k+i+1,2*n+k+j,1,0)    
    return -solver.MinCost(0,2*n+2*k+1,k)

ans=0
k=1
while True:
    tmp=solve(k)
    ans=max(ans,tmp)
    if tmp==-1 or k==n:
        break
    k+=1
print(ans)

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

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


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

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

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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int a, b, c, d; cin >> a >> b >> c >> d;
    int ans = min(b, d) - max(a, c);
    cout << max(ans, 0) << endl;

    return 0;
}


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

int main(void)
{
    int count=0;
    char s[200001]={},t[200001]={};
    scanf("%s",s);
    scanf("%s",t);

    for(int i=0;i<strlen(s);i++){
        if(s[i]!=t[i]) count+=1;
    }
    printf("%d",count);
    return 0;
}


Measured memory_bytes: 2096
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    s,t=map(str,input().split())
    a=t+s
    print(a)











if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int64_t i = 0; i < n; ++i)
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  bool c = 1;
  vector<vector<char>> a(n, vector<char>(n)), b(m, vector<char>(m));
  rep(i, n){
    string s;
    cin >> s;
    rep(j, n) a[i][j] = s[j];
  }
  rep(i, m){
    string s;
    cin >> s;
    rep(j, m) b[i][j] = s[j];
  }
  rep(i, n-m){
    rep(j, n-m){
      c = 1;
      rep(k, m){
        rep(l, m){
          if(a[i+k][j+l] != b[k][l]){
            c = 0;
            break;
          }
        }
        if(!c) break;
      }
      if(c) break;
    }
    if(c) break;
  }
  if(c) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256