akhauriyash/Code-Regression huggingface dataset:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = input()
    t = input()
    ans = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 70468
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
template <class T> void ckmax(T &x,const T y){
	if (x<y)
		x=y;
}
template <class T> void ckmin(T &x,const T y){
	if (x>y)
		x=y;
}
const int mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
const int N=1<<18,S=N*20*2;
int n,s;
int val[N],ival[N];
int lp[N],rp[N];
int ans=0;
int tmp;
namespace seg{
	int cnt=0;
	int val[S],ls[S],rs[S],xp[S];
	int ins(int rt,int x,int p,int v){
		if (!rt)
			rt=++cnt,xp[rt]=x;
		Add(val[rt],v);
		if (x>=(1<<n)){
			assert(x==p);
			return rt;
		}
		if (p<=rp[x*2])
			ls[rt]=ins(ls[rt],x*2,p,v);
		else
			rs[rt]=ins(rs[rt],x*2+1,p,v);
		return rt;
	}
	int merge(int x,int y,int a){
		if (!x||!y)
			return x|y;
		if (a>=(1<<n)){
			int rt=++cnt;
			val[rt]=Add(val[x]+val[y]);
			xp[rt]=a;
			return rt;
		}
		int rt=++cnt;
		xp[rt]=a;
		Add(tmp,(LL)val[ls[x]]*val[rs[y]]%mod*ival[a]%mod*ival[a/2]%mod);
		Add(tmp,(LL)val[rs[x]]*val[ls[y]]%mod*ival[a]%mod*ival[a/2]%mod);
		val[rt]=Add(val[x]+val[y]);
		ls[rt]=merge(ls[x],ls[y],a*2);
		rs[rt]=merge(rs[x],rs[y],a*2+1);
		return rt;
	}
}
int p[N];
void dfs(int x,int v){
	v=(LL)v*x%mod;
	val[x]=v;
	ival[x]=Pow(v,mod-2);
	if (x>=(1<<n)){
		lp[x]=rp[x]=x;
	}
	else {
		int l=x*2,r=l+1;
		dfs(l,v);
		dfs(r,v);
		lp[x]=lp[l];
		rp[x]=rp[r];
	}
}
int rt[N];
void solve(int x){
	if (x>=(1<<n)){
		rt[x]=seg::ins(rt[x],1,p[x],(LL)val[x]*val[p[x]]%mod);
		return;
	}
	int l=x*2,r=l+1;
	solve(l);
	solve(r);
	tmp=0;
	rt[x]=seg::merge(rt[l],rt[r],1);
	Add(ans,(LL)tmp*ival[x/2]%mod*ival[x]%mod);
}
int main(){
	n=read()-1;
	s=(1<<(n+1))-1;
	val[0]=ival[0]=1;
	dfs(1,1);
//	outarr(val,1,s);
//	outarr(ival,1,s);
	For(i,(1<<n),s)
		p[i]=read()+(1<<n)-1;
	solve(1);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 78848
#include<bits/stdc++.h>
using namespace std;
const int maxn=4040,p=924844033;
int fac[maxn],dp[maxn][maxn][2],a[maxn],g[maxn],n,k,tot;
int main(){
	cin>>n>>k;
	fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%p;
	for(int i=1;i<=k;++i){
		for(int j=i;j<=n;j+=k)a[++tot]=j;
        for(int j=i;j<=n;j+=k)a[++tot]=j;
	}
	dp[1][0][0]=1;
	for(int i=2;i<=tot;++i)
		for(int j=0;j<=min(n,i/2);++j){
			dp[i][j][0]=(dp[i-1][j][1]+dp[i-1][j][0])%p;
			if(j>0&&a[i]-a[i-1]==k)dp[i][j][1]=dp[i-1][j-1][0];
		}
	for(int i=0;i<=n;++i)g[i]=1ll*(dp[tot][i][0]+dp[tot][i][1])*fac[n-i]%p;
	int ans=0;
	for(int i=0;i<=n;++i){
		if(i&1)ans=(ans+p-g[i])%p;else ans=(ans+g[i])%p;
	}
	cout<<ans;
}

Measured memory_bytes: 125440
using System;

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            int count;

            while (true)
            {
                count = 0;
                string[] str = Console.ReadLine().Split(' ');
                int n = int.Parse(str[0]);
                int x = int.Parse(str[1]);
                if (n == 0 && x == 0) { break; }
                for (int i = 1; i <= n; i++)
                {
                    for (int j = 1; j <= n; j++)
                    {
                        for (int k = 1; k <= n; k++)
                        {
                            if (i != k && k != j && i != j && i + j + k == x)
                            {
                                count++;
                            }
                        }
                    }
                }
                Console.WriteLine(count / 6);
            }

            Console.ReadLine();
        }
    }
}














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

int main()
{
    int N;
    cin >> N;
    vector<int> X(N);
    rep(i,N){
        cin >> X[i];
    }
    ll total = 0;
    ll ans = 100000000;
    rep(i,101){
        rep(j,N){
            total += pow(X[j]-i,2);
        }
        if(ans > total) ans = total;
        total = 0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ROOP(i, N) for(int i=0; i<N; i++)
#define RVROOP(i, N) for(int i=N; i>=0; i--)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main(){
  int H,N; cin>>H>>N;
  int score=0;
  for(int i=0; i<N; i++){
    int x; cin>>x;
    score+=x;
  }
  if(score<H){
    cout<<"No"<<endl;
  }  
  else{
    cout<<"Yes"<<endl;
  }
}

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

using namespace std;

int H, W;
int N;
int sr, sc;
string S, T;

bool Solve(int init, int M, char dec, char inc) {
  int p = init;
  for (int i = 0; i < N; ++i) {
    if (S[i] == inc) ++p;
    if (p > M) return true;
    if (T[i] == dec && p > 1) --p;
  }
  p = init;
  for (int i = 0; i < N; ++i) {
    if (S[i] == dec) --p;
    if (p <= 0) return true;
    if (T[i] == inc && p < M) ++p;
  }
  return false;
}

int main() {
  while(cin >> H >> W >> N) {
    cin >> sr >> sc;
    cin >> S >> T;
    bool ans = Solve(sr, H, 'U', 'D') || Solve(sc, W, 'L', 'R');
    cout << (ans ? "NO" : "YES") << endl;
  }
}


Measured memory_bytes: 776
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner x = new Scanner(System.in);
      String sa = x.next();
      String sb = x.next();
      String sc = x.next();
      int ca = 0;
      int cb = 0;
      int cc = 0;
      int turn = 0;
      while(true){
      	if(turn==0){
          if(sa.substring(ca,ca+1).equals("a"))turn=0;
          else if(sa.substring(ca,ca+1).equals("b"))turn=1;
          else turn = 2;
          ca++;
        }
        else if(turn==1){
          if(sb.substring(cb,cb+1).equals("a"))turn=0;
          else if(sb.substring(cb,cb+1).equals("b"))turn=1;
          else turn = 2;
          cb++;
        }
        else if(turn==2){
          if(sc.substring(cc,cc+1).equals("a"))turn=0;
          else if(sc.substring(cc,cc+1).equals("b"))turn=1;
          else turn = 2;
          cc++;
        }
        if(ca==sa.length()&&turn==0){
        	System.out.println("A");
          return;
        }
        if(cb==sb.length()&&turn==1){
        	System.out.println("B");
          return;
        }
        if(cc==sc.length()&&turn==2){
        	System.out.println("C");
          return;
        }
      }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using ll = long long;
const ll INF = (ll)1e18L;
const int NMAX = 100100;
template<class X, class Y> X& remin(X& x, Y y) { return x = (y < x ? y : x); }
template<class X, class Y> X& remax(X& x, Y y) { return x = (y > x ? y : x); }
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    for (int n, W; std::cin >> n >> W; ) {
        std::vector<ll> dp(1 + 1000 * n, INF);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int w, v; std::cin >> w >> v;
            for (int curr = 1000 * n; curr >= v; curr--) {
                remin(dp[curr], dp[curr-v] + w);
            }
        }
        int answ = 1000 * n;
        while (answ >= 0 && dp[answ] > W) answ--;
        assert(answ >= 0);
        std::cout << answ << std::endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb emplace_back
typedef long long ll;
using namespace std;
ll n , k;
ll a[100005];
int main()
{
        cin >> n >> k;
        for(ll i=1;i<=n;i++) cin >> a[i];
        ll ans = 1;
        n -= k;
        ans = ans + ((n + k - 2) / (k-1));
        cout << ans << endl;
        return 0;
}


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

int main(){
    long long int n, x;
    cin >> n >> x;

    vector<pair<long long int, 
                pair<long long int, 
                     pair<long long int, long long int>>>> test(n);

    for(int i=0; i<n; i++){
        long long int b, l, u;
        cin >> b >> l >> u;

        test[i] = {(x-b) * u + b * l, {b, {l,u}}};
    }
    sort(test.begin(), test.end());
    reverse(test.begin(), test.end());

    // cumulative sum
    vector<long long int> csum1(n+1), csum2(n+1);
    for(long long int i=0; i<n; i++){
        long long int b = test[i].second.first;
        long long int l = test[i].second.second.first;
        long long int u = test[i].second.second.second;

        csum1[i+1] = csum1[i] + (x-b) * u;
        csum2[i+1] = csum2[i] + b * l;
    }

    long long int lower = -1, upper = x * n, mid;
    while(upper - lower > 1){
        mid = (upper + lower) / 2;
        long long int score = -1;

        for(long long int i=0; i<n; i++){
            long long int diff = 0;
            long long int a = mid % x;
            if(a == 0) diff = csum1[mid/x] + (csum2[n] - csum2[mid/x]);
            else{
                long long int b = test[i].second.first;
                long long int l = test[i].second.second.first;
                long long int u = test[i].second.second.second;
                if(a < b) diff = l * (a - b);
                if(a > b) diff = u * (a - b);

                if(i >  mid/x) diff += csum1[mid/x] - (csum2[n] - csum2[mid/x] - b * l);
                if(i <= mid/x) diff += (csum1[mid/x + 1] - (x-b) * u) - (csum2[n] - csum2[mid/x + 1]);
            }
            score = max(score, diff);
        }
        if(score <  0) lower = mid;
        if(score >= 0) upper = mid;
    }
    cout << upper << endl;
    return 0;
}

Measured memory_bytes: 7988
//MD. HASNAIN ALI (UNSOLVED)
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int,int>

#define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
#define MAX3(a,b,c) max(a,max(b,c))
#define SQ(x) ((x) * (x))
#define SWAP(a,b) {        \
                    a=a+b; \
                    b=a-b; \
                    a=a-b; }

using namespace std;


int main()
{

    int a,b;
    cin>>a>>b;
    cout<<a*b<<endl;

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#ifdef PRAGMA
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#define fst first
#define snd second
#define fore(i,a,n) for(ll i=a;i<n;i++)
#define rfore(i, a, b) for(ll i = b - 1; i >= (ll)a; i--)
#define pb push_back
#define mp make_pair
#define bs binary_search
#define mm(a,b) memset(a,b,sizeof(a));
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(n) ((int) (n).size())
#define INFI ((ll)1e9)
#define MINI ((ll)-1e15)
#define EPS 1e-9
#define endl "\n"
using namespace std;
typedef long long ll;  
typedef long double ld;
const ll MOD = 1e9+7;     
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b,a%b); } 
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const ll MAXN =300005;
ll n,t,q,x,s,k,m,h;
int dp[10001];
int a[1001], b[1001];
int solve(int h){
    if(h<=0)return 0;
    int &r = dp[h];
    if(~r)return r;
    r = INFI;
    fore(i,0,n)r = min(r,b[i]+solve(h-a[i]));
    return r;
}
int main(){
    cin >> h >> n;
    fore(i,0,n)cin>>a[i]>>b[i];
    mm(dp,-1);
    cout << solve(h);
    return 0;
}


Measured memory_bytes: 768
class Heap
    attr_reader :size
    def initialize
        @heap = []
        @size = 0
    end

    def length
        @size
    end

    def push(x)
        i = @size
        @size += 1
        while i > 0
            p = (i - 1) / 2
            break if @heap[p] <= x
            @heap[i] = @heap[p]
            i = p
        end
        @heap[i] = x
        self
    end

    def pop
        return nil if @size == 0
        ret = @heap[0]
        @size -= 1
        x = @heap[@size]
        i = 0
        while i * 2 + 1 < @size
            a = i * 2 + 1
            b = a + 1
            if b < @size && @heap[b] < @heap[a]
                a = b
            end
            break if @heap[a] >= x
            @heap[i] = @heap[a]
            i = a
        end
        @heap[i] = x
        @heap.pop
        return ret
    end
end

class Array
    include Comparable
end

N = gets.to_i
neighbors = Array.new(N+1){{}}
(N-1).times do
    a, b = gets.split.map(&:to_i)
    neighbors[a][b] = true
    neighbors[b][a] = true
end

ans = Array.new(N+1)
heap = Heap.new
K = gets.to_i
K.times do
    v, pt = gets.split.map(&:to_i)
    ans[v] = pt
    heap.push([pt, v])
end

while heap.size > 0
    pt, v = heap.pop
    neighbors[v].each do |k, _|
        if ans[k]
            if (ans[k] - pt).abs != 1
                puts 'No'
                exit
            end
        else
            ans[k] = pt + 1
            heap.push([pt+1, k])
        end
    end
end

puts 'Yes'
puts ans[1, N]

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

using namespace std;

#define db(x) cerr << #x << " = " << x << endl

#define MAXN 112
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long

ll n, W;
ll w[MAXN];
ll v[MAXN];
int vis[MAXN][MAXN*1123];
ll dp[MAXN][MAXN*1123];

ll solve(int idx, ll money)
{
    if (idx == n)
        if (money == 0)
            return 0;
        else
            return INF;

    if (vis[idx][money])
        return dp[idx][money];
    vis[idx][money] = 1;

    return dp[idx][money] = min(solve(idx + 1, money), solve(idx + 1, money - v[idx]) + w[idx]);
}

int main()
{
    scanf("%lld%lld", &n, &W);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld%lld", &w[i], &v[i]);
    }

    for (int i = 100000; i >= 0; --i)
    {
        //db(i);
        if (solve(0, i) <= W)
            return !printf("%d\n", i);
    }
}


Measured memory_bytes: 149248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
ll a,b;
cin >> a>>b;
if(abs(a-b)%2){
    cout << "IMPOSSIBLE" << endl;
    return 0;
}
else{
    cout << abs(a-b)/2 +min(a,b) << endl;
    return 0;
}


}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	    	Scanner sc = new Scanner(System.in);
	    	String s = sc.next();
	    	int min = 1000;
	    	for (int i = 0; i < s.length() - 2; i++) {
			if (Math.abs(Integer.parseInt(s.substring(i, i+3)) - 753) < min) {
				min = Math.abs(Integer.parseInt(s.substring(i, i+3)) - 753);
			}
		}
	    	System.out.println(min);
	}
}


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

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

    int c = 0;
    char now = 'L';
    for (int i = 0; i < N; i++) {
        if (S[i] == now) {
           c++;
        } else {
            cnt.push_back(c);
            c = 1;
            if (now == 'R') now = 'L';
            else now = 'R';
        }
    }
    if (c != 0) cnt.push_back(c);
    if (cnt.size() % 2 != 0) cnt.push_back(0);

    int res = 0;
    int add = 2 * K + 1;
    int left = 0, right = 0, sum = 0;
    int max_left = 0, max_right = 0;
    for (int i = 0; i < cnt.size(); i++) {
        int next_left = i;
        int next_right = min(i + add, (int)cnt.size());

        while (next_left > left) {
            sum -= cnt[left++];
        }
        while (next_right > right) {
            sum += cnt[right++];
        }
        if (sum > res) {
            res = sum;
            max_left = left;
            max_right = right - 1;
        }
    }

    for (int i = 0; i < cnt.size(); i++) {
        if ((i < max_left || i > max_right) && cnt[i] > 1) {
            res += cnt[i] - 1;
        }
    }
    cout << res - 1 << endl;
    return 0;
}

Measured memory_bytes: 1020
# ABC141E - Who Says a Pun?
def resolve():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in memo:
                flg = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


resolve()


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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
}

int ans = 0;
bool check = 0;
string s, t;
int N = 3;
vector<int> v(N);
int a, b, c;
int x, y;
char ch;

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  cin >> a >> b;
  pr(square(a) - b);
}

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

template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}

int main(){
    string s, ans = "";
    cin >> s;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '0'){
            ans.push_back(s[i]);
        }else if(s[i] == '1'){
            ans.push_back(s[i]);
        }else if (s[i] == 'B' && ans.size() != 0){
            ans.pop_back();   
        }
    }
    cout << ans << endl;
    return 0;
}



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

int main() {
  int N;
  cin >> N;
  if (N<1 || N>1000){
    return 0;
  }
  int total = 0;
  for(int i=0; i<N; ++i){
    int l, r;
    cin >> l >> r;
    total += r - l + 1;
  }
  cout << total << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0

for i in range(n):
    if a[i] > b[i]:
        result += b[i]
        a[i] -= b[i]
        b[i] = 0

    else:
        result += a[i]
        
        b[i] -= a[i]
        a[i] = 0

        if a[i + 1] > b[i]:
            result += b[i]
            a[i + 1] -= b[i]
            b[i] = 0
        else:
            result += a[i + 1]
            b[i] -= a[i + 1]
            a[i + 1] = 0
    #print(a[i],b[i])
print(result)

Measured memory_bytes: 19004
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long
#define MOD 1000000007
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

class Counts {
public:
    long long x;
    long long y;
    long long count;
    bool operator < (const Counts &arg) const{
        return atan2(y, x) < atan2(arg.y, arg.x);
    }
};

ll gcd(ll a, ll b)
{
    if(a%b == 0) return b;

    return gcd(b, a%b);
}

long long mod_pow(const long long x, long long n, const long long mod) {
    long long res = 1;
    if (n == 0) return 1;
    if (n & 1) res = x;
    long long y = mod_pow(x, n >> 1, mod);
    res = (res * (y * y % mod)) % mod;
    return res;
}

map<pair<ll, ll>, int> counts;
int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int zero_zero = 0;
    ll ret = 1;
    for(int i=0;i<n;++i)
    {
        ll a, b;
        cin >> a >> b;
        if(a==0 && b==0){
            zero_zero++;
            continue;
        }
        if(a==0 || b == 0)
        {
            if(a==0) b = 1;
            if(b==0) a = 1;
            counts[MP(a,b)]++;
            continue;
        }

        if(b < 0)
        {
            a *= -1;
            b *= -1;
        }
        ll _gcd = gcd(abs(a), abs(b));
        counts[MP(a/_gcd, b/_gcd)]++;
    }

    for(auto& tmp: counts)
    {
        ll x = tmp.first.first;
        ll y = tmp.first.second;
        ll count_a = tmp.second;
        ll count_b = counts[MP(-y, x)] + counts[MP(y, -x)];

        ret *= (mod_pow(2, count_a, MOD) + mod_pow(2, count_b, MOD)) - 1;
        ret %= MOD;

        tmp.second = 0;
        counts[MP(-y, x)] = 0;
        counts[MP(y, -x)] = 0;
    }

    ret += zero_zero;
    ret %= MOD;
    ret -= 1;
    if(ret < 0) ret += MOD;
    cout << ret << endl;
}

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

int main()
{
	string p, s;
	cin >> s >> p;
	bool flag = false;
	s += s;
	size_t pos = s.find(p);
	if(pos == string::npos)
		cout << "No" << endl;
	else
		cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 3204
#include <iostream>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    char t[q], d[q];
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> d[i];
    }

    int left, right;
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        int pos = mid;
        bool flag = true;
        for (int i = 0; i < q; i++) {
            if (t[i] == s[pos]) {
                if (d[i] == 'L') {
                    pos--;
                } else {
                    pos++;
                }
            }

            if (pos == -1) {
                flag = false;
                break;
            } else if (pos == n) {
                break;
            }
        }

        if (flag) {
            r = mid;
        } else {
            l = mid;
        }
    }
    left = r;

    l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        int pos = mid;
        bool flag = true;
        for (int i = 0; i < q; i++) {
            if (t[i] == s[pos]) {
                if (d[i] == 'L') {
                    pos--;
                } else {
                    pos++;
                }
            }

            if (pos == n) {
                flag = false;
                break;
            } else if (pos == -1) {
                break;
            }
        }

        if (flag) {
            l = mid;
        } else {
            r = mid;
        }
    }
    right = l;

    cout << right - left + 1 << endl;

    return 0;
}


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

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

    int n_ABC = 0;
    for (int i = 0; i < (N - 2); i++) {
        if (S.compare(i, 3, "ABC") == 0) {
            n_ABC++;
        }
    }
    cout << n_ABC << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    vector<int> a;
    for (int i = 0; i < 3; i++) {
        int e;
        cin >> e;
        a.pb(e);

    }


    sort(a.begin(), a.end());
    cout << a[0] + a[1];







}




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

#define all(n) n.begin(),n.end()
#define ll long long

#define pb push_back
#define eb emplace_back
#define endl "\n"
#define pll pair<ll,ll>
#define ff first
#define ss second

using namespace std;
const ll maxn=3e3+120;
const ll maxx=1e16;
const ll mod1=1e9+7;
const ll mod=998244353;
vector<ll> adj[maxn];
ll dp[maxn][maxn];
ll n, m ;
ll mu(ll a ,ll n ,ll mod )
{
    if (n==0) return 1;
    if (n==1) return a;
    ll t= mu(a,n/2,mod);
    if (n%2==0)
    {
        return ( t%mod *t%mod )%mod ;
    }
     return (a%mod * t%mod *t%mod )%mod ;
}
ll f(ll n1, ll m1)
{
  if (n1==n&&m1==m) return 1;
  if (dp[n1][m1]!=-1) return dp[n1][m1];
  ll ans;
   if (n1==n)
   {
       ans=(f(n1,m1+1)%mod *n1%mod )%mod;
   }
   else if (m1==m)
   {
       ans=(f(n1+1,m1)%mod *m1%mod  )%mod;
   }
   else
   {
         ans = (n1*f(n1,m1 + 1) + m1*f(n1 + 1,m1) - n1*m1*f(n1 + 1,m1 + 1) + mod*mod)%mod;
     //  dp[n1][m1]=((((f(n1+1,m1)%mod *(m1)%mod  )%mod+(f(n1,m1+1)%mod *(n1)%mod )%mod-n1%mod *m1%mod *f(n1+1,m1+1)%mod +mod *mod )))%mod;
   }
   return dp[n1][m1]=ans;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("TEAMS.INP","r"))
    {
        freopen("TEAMS.INP", "r", stdin);
        freopen("TEAMS.OUT", "w", stdout);
    }
    ll a, b;
    cin>>a>>b>>n>>m ;
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=m;j++)
        {
            dp[i][j]=-1;
        }
    }
    cout <<f(a,b);



}


Measured memory_bytes: 77212
using System;

namespace ABC068
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(ABCxxx.AttachABC(Console.ReadLine()));
        }
    }
  
  public class ABCxxx
    {
        public static string AttachABC(string n)
        {
            return "ABC" + n;
        }
    }
}

Measured memory_bytes: 25888
#include<iostream>
#include <string>

int main(){
	std::string s;
	std::cin >> s;
	int n=s.size();
	bool C, F;
	C=F=false;
	for(int i=0;i<n;i++){
		if(s[i]=='C'){
			C=true;
		}
		if(C && s[i]=='F'){
			F=true;
		}
	}
	if(F){
		std::cout << "Yes" <<std::endl;
	}else{
		std::cout<<"No" <<std::endl;
	}
}

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

using namespace std;


void solve() {
    long long N, A, B; cin >> N >> A >> B;
    long long C = A + B;
    long long ans = N / C * A + min(N % C, A);
    cout << ans << endl;
}


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

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include <cassert>
#include<string>
#define rep(i,rept) for(long long i = 0; i <(long long)rept;i++)
using namespace std;
int main() {
	int a = 0, b = 0, c = 0, d[100000], e[100000], f = 0, g = 0, h = 0, count = 0,x=0,y=0,z=0;
	char rikka, toka[100000];
	string saya, homu, kyok, mami, mado[50];
	bool gg = true;
	int manji, nk[26] = { false };
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> d[i];
	}
	for (int j = 0; j < a; j++) {
		if (d[j] == 1) {
			b++;
		}
		else { b = 0; }
		count = max(count, b);
	}
	cout << count + 1 << endl;
	return 0;
}



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

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

  int n;
  cin >> n;

  cout << ((n + 999) / 1000) * 1000 - n << endl;

  return (0);
}


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

#define int long long int

void fileioe(){
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout); 
	freopen("error.txt","w",stderr);
}
#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
#define fioe() fileioe()
#else
#define fioe() 1
#endif
//!
const int maxr = 2e3+5;
vector<pair<int,int> >  arr;
int dp[maxr][maxr];

int solve(int idx,int i, int j){
	if(idx == arr.size()){
		return 0;
	}
	int & ans = dp[i][j];
	if(ans > -1)
		return ans;
	int val = arr[idx].first; 
	int ind = arr[idx].second;
	ans = max(ans , solve(idx+1,i+1,j) + abs(i - ind)*val);
	ans = max(ans , solve(idx+1,i,j-1) + abs(j - ind)*val);
	return ans;
}

int32_t main()
{
	GO
	//fioe();
	int n;
	cin>>n;
	for(int i = 0;i < n; i++){
		int a;
		cin >> a;
		arr.push_back({a,i});
	}
	memset(dp,-1,sizeof(dp));
	sort(arr.begin(),arr.end());
	reverse(arr.begin(),arr.end());
	int ans = solve(0,0,n-1);
	cout << ans << endl;
	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> X(M);
  for (int i = 0; i < M; i++) cin >> X[i];
  sort(X.begin(), X.end());
  int res = 0;
  if (N >= M) cout << res << endl;
  else {
    vector<int> sub(M-1);
    for (int i = 0; i < M-1; i++) {
      sub[i] = X[i+1] - X[i];
    }
    sort(sub.begin(), sub.end());
    for (int i = 0; i < (M-N); i++) res += sub[i];
    cout << res << endl;
  }
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	int ans=0;
	ans+=min(a,d);
	d-=min(a,d);
	d-=min(b,d);
	ans-=min(c,d);
	d-=min(c,d);
	cout << ans;
	return 0;
}

Measured memory_bytes: 3192
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 10**6

# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

def mod_nPr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] % MOD
    return tmp * fac[n] % MOD

n, m = map(int, input().split())
ans = 0
for i in range(n+1):
    ans += mod_nCr(n, i) * mod_nPr(m-i, n-i) * (-1)**i % MOD
ans *= mod_nPr(m, n)
print(ans % MOD)

Measured memory_bytes: 98944
#include<bits/stdc++.h>
#define LLI long long int
#define ULTRA 2134567890
#define debug(x) if(MODE==x)
#define MODE 0
using namespace std;

int main()
{
    int i,j;

    int n;
    scanf("%d",&n);
    printf("%d\n",n*n*n);

    return 0;
}


Measured memory_bytes: 256
mat = Array.new(14){Array.new(14){0}}
while input = gets
  x, y, s = input.split(",").map(&:to_i)
  x += 2
  y += 2
  mat[x][y] += 1
  mat[x+1][y] += 1
  mat[x][y+1] += 1
  mat[x-1][y] += 1
  mat[x][y-1] += 1
  if s > 1
    mat[x+1][y+1] += 1
    mat[x+1][y-1] += 1
    mat[x-1][y+1] += 1
    mat[x-1][y-1] += 1
  end
  if s > 2
    mat[x+2][y] += 1
    mat[x-2][y] += 1
    mat[x][y+2] += 1
    mat[x][y-2] += 1
  end
end
 
max = 0
white = 0
10.times{|i|
  10.times{|j|
    max = mat[i+2][j+2] if mat[i+2][j+2] > max
    white += 1 if mat[i+2][j+2] == 0
  }
}
puts white
puts max

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b&&a!=c||a==c&&a!=b||b==c&&b!=a){
    cout << "Yes" << endl;
  }else{cout << "No" << endl;}
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Console;

namespace CPLib
{
    class Atria
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            WriteLine(1000 -(n%1000) == 1000 ? 0: 1000 - (n % 1000));
        }
    }
}


Measured memory_bytes: 27536
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n;
  cin >> n;
  
  int ans=0;
  
  if(n==10||n==100||n==1000||n==10000||n==100000) ans=10;
  
  else{
    ans = n%10 + (n/10)%10 + (n/100)%10 + (n/1000)%10 + (n/10000)%10;
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if(a < c)
        a = c;
    if(b > d)
        b = d;
    if(a < b)
        printf("%d\n",b-a);
    else
        printf("0\n");
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<utility>
#include<functional>
#include<cassert>
#include<cmath>
#include<math.h>
#include<unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<vint> vvint;
#define PI 3.1415926535
#define MOD 1000000007
#define rep(i, n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define MAX ((ll)1<<(ll)31)-1
int H, W;
vector<P> a(4);
vector<vector<char>> s;

int dfs(int i, int j) {
	vector <vector< bool >> flag(H + 2, vector<bool>(W + 2, false));
	vector<vector<int>> d(H + 2, vector<int>(W + 2));
	int m = 0;
	queue<P> q;
	q.push(P(i, j));
	d[i][j] = 0;
	while (q.size() != 0) {
		P now = q.front(); q.pop();
		flag[now.first][now.second] = true;
		rep(k, 4) {
			int x = now.first + a[k].first,y= now.second + a[k].second;
			if (s[x][y] == '.' && d[x][y] == 0) {
				q.push(P(x, y));
				d[x][y] = d[now.first][now.second] + 1;
				m = max(m, d[x][y]);
			}
		}
		d[now.first][now.second] = -1;
	}
	return m;

}


int main(void) {
	H, W; cin >> H >> W;
	s.resize(H + 2, vector<char>(W + 2));
	a = { P(0, -1), P(1, 0), P(0, 1), P(-1, 0) };
	int ans = 0;

	rep(i, H + 2) {
		s[i][0] = s[i][W + 1] = '#';
	}
	rep(i, W + 2) {
		s[0][i] = s[H + 1][i] = '#';
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> s[i][j];
		}
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (s[i][j] == '.') {
				ans = max(ans, dfs(i, j));
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int n,k,l[N],r[N],tot,x,y,a[N*2],len;
ll sum,f[N],ans=1e18;
int cost(int s,int t){
	return s<=t?t-s:t+k-s;
}
struct Tree{
	int l,r,num;
}T[N*4];
void build(int x,int l,int r){
	T[x].l=l;T[x].r=r;
	if (l==r)return;
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
}
void down(int x){
	if (T[x].num){
		T[x*2].num=T[x*2+1].num=T[x].num;
		T[x].num=0;
	}
}
void insert(int x,int l,int r,int z){
	if (T[x].l>r||l>T[x].r)return;
	if (T[x].l>=l&&T[x].r<=r){
		T[x].num=z;
		return;
	}
	down(x);
	insert(x*2,l,r,z);
	insert(x*2+1,l,r,z);
}
int find(int x,int y){
	if (T[x].l==T[x].r)return T[x].num;
	down(x);
	int mid=(T[x].l+T[x].r)/2;
	if (y<=mid)return find(x*2,y);
	return find(x*2+1,y);
}
int ef(int x){
	int l=1,r=tot;
	while (l<r){
		int mid=(l+r)/2;
		if (a[mid]<x)l=mid+1;
		else r=mid;
	}
	return l;
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1,la=0;i<=n;i++){
		scanf("%d%d",&x,&y);
		sum+=x;
		if (y==1&&2*x>k){
			puts("-1");
			return 0;
		}
		x=((k-x%k)<<1)%k;
		if (y==1)l[i]=la,r[i]=(la+x)%k;
		else l[i]=0,r[i]=k-1;
		la=(la+x)%k;
	}
	a[++len]=0;a[++len]=k-1;
	for (int i=1;i<=n;++i)a[++len]=l[i],a[++len]=r[i];
	sort(a+1,a+len+1);
	tot=1;
	for (int i=2;i<=len;i++)
		if (a[i]!=a[tot])a[++tot]=a[i];
	build(1,1,tot);
	for (int i=n;i;i--){
		l[i]=ef(l[i]);r[i]=ef(r[i]);
		int x=find(1,l[i]);
		if (x)f[i]=f[x]+cost(a[l[i]],a[l[x]]);
		if (l[i]<=r[i]){
			if (l[i]>1)insert(1,1,l[i]-1,i);
			if (r[i]<tot)insert(1,r[i]+1,tot,i);
		}
		else if (r[i]+1<l[i])insert(1,r[i]+1,l[i]-1,i);
	}
	for (int i=1;i<=tot;i++){
		int x=find(1,i);
		if (x)ans=min(ans,f[x]+cost(a[i],a[l[x]]));
		else ans=0;
	}
	printf("%lld\n",ans+sum*2);
	return 0;
}


Measured memory_bytes: 7296
#include<bits/stdc++.h>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define LL long long
#define inf (2147483647)
using namespace std;
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-48;
    x*=f;
}
int n,s,m,t;
int wans,ans;
struct ha{int to,c,w,fan;};
vector<ha>e[6010]; 
void jb(int x,int y,int c,int w){
	e[x].push_back((ha){y,c,w,e[y].size()});
	e[y].push_back((ha){x,0,-w,e[x].size()-1});
}
int dis[6010],indl[6010],dl[10000010],fr[6010],fri[6010];
bool spfa(){
	int l=1,r=0;
	for(int i=1;i<=t;++i) dis[i]=inf;
	dis[s]=0;
	dl[++r]=s; indl[s]=1;
	while(l<=r){
		int x=dl[l]; ++l; indl[x]=0;
		int si=e[x].size();
		for(int i=0;i<si;++i){
			ha u=e[x][i];
			if(u.c&&dis[u.to]>dis[x]+u.w){
				dis[u.to]=dis[x]+u.w; fr[u.to]=x; fri[u.to]=i;
				if(!indl[u.to]) indl[u.to]=1,dl[++r]=u.to;
			}
		}
	}
	if(dis[t]==inf) return 0;
	int x=t,mf=inf;
	while(x!=s){
		int y=fr[x];
		mf=min(mf,e[y][fri[x]].c);
		x=y;
	}
	x=t; ans+=mf;
	while(x!=s){
		int y=fr[x];
		e[y][fri[x]].c-=mf;
		e[x][e[y][fri[x]].fan].c+=mf;
		wans+=e[y][fri[x]].w*mf;
		x=y;
	}	
	return 1;
}
inline int zh(int i,int j) {return i*m+j+1;}
string mp[55];
int main(){
	read(n);read(m);s=n*m+1;t=n*m+2;
	for(int i=0;i<n;++i) cin>>mp[i];
	//init();
	for(int i=0;i<n;++i) 
		for(int j=0;j<m;++j)
			if(mp[i][j]=='.') jb(zh(i,j),t,1,0);
			else if(mp[i][j]=='o') jb(zh(i,j),t,1,0),jb(s,zh(i,j),1,0);
	for(int i=0;i<n;++i) 
		for(int j=0;j<m;++j)
		if(mp[i][j]!='#'){
			if(i+1!=n) if(mp[i+1][j]!='#') jb(zh(i,j),zh(i+1,j),inf,-1);
			if(j+1!=m) if(mp[i][j+1]!='#') jb(zh(i,j),zh(i,j+1),inf,-1);

		}
	while(spfa());
	cout<<-wans<<endl;
    return 0;	
}

Measured memory_bytes: 4200
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  ll ans = 1;
  rep(i, n) ans = (ans * 10) % MOD;
  ll katahou = 1;
  rep(i, n) katahou = (katahou * 9) % MOD;
  ll both = 1;
  rep(i, n) both = (both * 8) % MOD;
  ans = (ans - (katahou * 2 - both)) % MOD;
  ans = (ans + MOD) % MOD;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 30;
#define FOR(i,k,n) for(int i=(k);i<(n);++i)

int N,M,R;
ll d[205][205];

void floyd(){

    FOR(k,0,N){
        FOR(i,0,N){
            FOR(j,0,N){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }

    return;
}

int main(){
    cin >> N >> M >> R;

    FOR(i,0,N){
        FOR(j,0,N){
            d[i][j] = INF;
        }
        d[i][i]=0LL;
    }

    vector<int> v(R);
    FOR(i,0,R){
        cin >> v[i];
        v[i] -= 1;
    }
    sort(v.begin(),v.end());

    int s,t;
    ll u;

    FOR(i,0,M){
        cin >> s >> t >> u;
        s -= 1; t -= 1;
        d[s][t] = u;
        d[t][s] = u;
    }

    floyd();

    ll res = INF;

    do{
        ll tmp = 0LL;
        FOR(i,0,R-1){
            tmp += d[v[i]][v[i+1]];
        }
        res = min(res,tmp);
    }while(next_permutation(v.begin(),v.end()));

    cout << res << endl;

    return 0;
}


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

cout<<dp[n-1];

}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
const int MOD = 1000000007;
int main() {
    string s;
    cin>>s;
    if (s=="AAA"||s=="BBB")
    {
        /* code */
        cout<<"No"<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
    }
    
    
    }

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//これを使うときにはCOMinit();を忘れずに

int main(void){
    COMinit();
    ll N, K; cin >> N >> K;
    if(K >= N-1) K = N-1;
    ll ans = 0;
    for(int i = 0; i <= K; i++){
        ans = (ans + (COM(N, i)*COM(N-1, i) % MOD)) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12160
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main (){
    let n = read::<usize>();
    let mut i:usize = 1;
    loop {
        if i * i  > n { break;}
        i += 1;
    }
    println!("{}",(i-1)*(i-1));
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string N;
    getline(cin, N);

    long long a = 0;

    for (int i = 0; i < N.length(); i++)
    {
        a = a + N[i] - '0';
    }

    string ans;
    if (a % 9 == 0)
    {
        ans = "Yes";
    }
    else
    {
        ans = "No";
    }

    cout << ans << "\n";
}


Measured memory_bytes: 3268
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define d double
#define INF INT_MAX
#define output for(int i=0;i<sizex;i++) { for(int j=0;j<sizey;j++) { cout << moveChart[i][j] << " "; }cout<<endl; }cout<<endl;

int n, M;
int arr[100001];
int pref[100001];

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

    cin >> n >> M;
    int sum = 0;
    for(int i=0;i<n;i++){
        cin >> arr[i]; arr[i] %= M;
        sum += arr[i] % M; sum %= M;
        pref[i] = sum % M;
    }

    map <int, int> appearances; // appearances[0] = 1;
    ll counter = 0;
    for(int i=0;i<n;i++){
        if( !pref[i] ) counter++;
        counter += appearances[pref[i]];
        appearances[pref[i]]++;
    }

    cout << counter << endl;

}

Measured memory_bytes: 3968
import itertools

n = int(input())

order = list(itertools.permutations([int(x)for x in range(1,n+1)]))
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]

for i in range(len(order)):
    if P == list(order[i]):
        P_num = i
    if Q == list(order[i]):
        Q_num = i
        
print(abs(P_num-Q_num))

Measured memory_bytes: 8052
#!/usr/bin/env python3
def main():
    import time

    N = int(input())
    A = [int(x) for x in input().split()]

    num_lst = [0] * (N + 1)
    for a in A:
        num_lst[a] += 1

    ans = 0
    for num in num_lst:
        # ans += comb(num, 2, exact=True)
        ans += num * (num - 1) // 2

    start = time.time()
    for a in A:
        print(ans - (num_lst[a] - 1))
    end = time.time() - start
    # print(f'{end:6f}', 's')


if __name__ == '__main__':
    main()


Measured memory_bytes: 100896
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

N = int(input())

# 複数個の数値を、intの配列として取得
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans+=min(A[i],B[i])
    B[i]=max(0,B[i]-A[i])
    ans+=min(A[i+1],B[i])
    A[i+1]=max(0,A[i+1]-B[i])

print(ans)

Measured memory_bytes: 18752
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
long long int c = 1000000000000000000;
int main() {
    long long a;
    long double b;
    cin>>a>>b;
    cout<<(long long int)(a*b)<<endl;
}

Measured memory_bytes: 3728
var
i:integer;
p:boolean;
s:string;
begin
read(s);
if pos('C',s)<>0 then
  begin
    p:=true;
    for i:=pos('C',s)+1 to length(s) do
      if s[i]='F' then begin write('Yes');p:=false;break;end;
    if p then write('No');
  end
  else write('No');
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a(n);
	vector<int> ans(n);
	vector<pair<int, int>> b(m);
	for( int i = 0; i < n; ++i ) cin >> a[i].first >> a[i].second;
	for( int i = 0; i < m; ++i ) cin >> b[i].first >> b[i].second;
	for( int i = 0; i < n; ++i ){
		int mindist = INF;
		for( int j = 0; j < m; ++j ){
			int candy = abs( a[i].first-b[j].first ) + abs( a[i].second-b[j].second );			
			if( candy < mindist ){
				ans[i] = j;
				mindist = candy;
			}
		}
	}
	for( int i = 0; i < n; ++i ){
		cout << ans[i]+1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256