akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define y1 wzpakking
#define fi first
#define se second
#define BG begin
#define ED end
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?(x)-=mo:233)%s
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define sqr(x) (1ll*x*x)
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
#define INF (1ll<<60)
using namespace std;
int n,Q;
char S[1000005];
int main(){
	scanf("%d%s",&n,S+1);
	scanf("%d",&Q);
	while (Q--){
		int k,laM=0,SD=0,SM=0;
		scanf("%d",&k);
		ll ans=0,sum=0;
		For(j,1,n){
			if (j>k){
				if (S[j-k]=='D') SD--,sum-=SM;
				if (S[j-k]=='M') SM--;
			}
			if (S[j]=='D') SD++;
			if (S[j]=='M') SM++,sum+=SD;
			if (S[j]=='C') ans+=sum; 
		}
		printf("%lld\n",ans);
	}
} 

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

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int main(){
    int H, W, K;
    cin >> H >> W >> K;

    vector<string> s(H);
    rep(i, H) cin >> s[i];

    vector<vector<int>> a(H, vector<int>(W));

    int k = 1;
    rep(i, H) {
        rep(j, W) {
            if (a[i][j] != 0) continue;
            if (s[i][j] != '#') continue;

            a[i][j] = k;
            int y = i - 1;
            while (0 <= y && a[y][j] == 0 && s[y][j] != '#') {
                a[y][j] = k;
                y--;
            }

            y = i + 1;
            while (y < H && a[y][j] == 0 && s[y][j] != '#') {
                a[y][j] = k;
                y++;
            }

            k++;
        }
    }

    rep(i, W - 1) {
        if (a[0][i + 1] == 0) {
            rep(j, H) {
                a[j][i + 1] = a[j][i];
            }
        }
    }

    for (int i = W - 1; i > 0; --i) {
        if (a[0][i - 1] == 0) {
            rep(j, H) {
                a[j][i - 1] = a[j][i];
            }
        }
    }

    rep(i, H) {
        rep(j, W) cout << a[i][j] << " ";
        cout << endl;
    }
}

Measured memory_bytes: 1280
const BKRT = "\n";
const SPAC = " ";
const NOSP = "";

function Main(input){
	input = [].concat(...input.trim().split(BKRT).map(a=>a.split(SPAC)));
  const strShift = ()=>input.shift();
  const intShift = ()=>~~input.shift();
  
  return ~~((a,b)=>Math.max(a+b,a-b,a*b))(intShift(),intShift());
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
-1000 1000
`);

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

#define MOD 10000007
#define f first
#define s second
#define es " "
#define pb push_back
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define ll long long int
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define sz(x) (int)x.size()
typedef pair<int, int> pii;

int n, k, q, x, resp[100005];

int main(){
    fastio;
    cin >> n >> k >> q;
    for(int i=1; i<=n; i++){
        resp[i]=k;
    }
    for(int i=0; i<q; i++){
        cin >> x;
        resp[x]++;
    }
    for(int i=1; i<=n; i++){
        //cout << resp[i] << endl;
        if(resp[i]-q>0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
	// your code goes here
	int r;
    cin >> r;
    if(r<1200) cout << "ABC" << endl;
    else if(r<2800) cout << "ARC" << endl;
    else cout << "AGC" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int a[105][105], b[105], c[105];
int main() {
   int n, m;
   cin >> n >> m;
   rep(i, n) rep(j, m) cin >> a[i][j];
   rep(i, m) cin >> b[i];
   rep(i, n) { rep(j, m) c[i] += a[i][j] * b[j]; }
   rep(i, n) cout << c[i] << endl;
   return 0;
}


Measured memory_bytes: 3140
from collections import deque
n,m = map(int, input().split())
p= list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
v = [-1 for i in range(n)]
s = 0
for i in range(n):
  if v[i]!=-1:
    continue
  s+=1
  v[i]=s
  d = deque([i])
  while len(d):
    x = d.popleft()
    for i in g[x]:
      if v[i] == -1:
        d.append(i)
        v[i]=s
ans=0
for i in range(n):
  if v[i]==v[p[i]-1]:
    ans+=1
print(ans)

Measured memory_bytes: 100508
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


S = a_int()

'''
dp[i,j] ... 問題文の条件を満たし和がiとなる数列の通りの総数。j回前に仕切りを立てた場合の。(j=2のときは2回前以前を示すことにする)

更新

# iに仕切りを立てるとき
dp[i, 0] += dp[i-1, 2] #ここから仕切りが立てられる

# iに仕切りを立てないとき
dp[i, 0] += 0 #立てないんだから
dp[i, 1] += dp[i-1,0]
dp[i, 2] += dp[i-1,1] + dp[i-1,2]
'''


from numba import njit


@njit('(i8,)', cache=True)
def solve(S):
    dp = np.zeros((S + 1, 3), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(1, S + 1):
        dp[i, 0] += dp[i - 1, 2] % MOD
        dp[i, 1] += dp[i - 1, 0] % MOD
        dp[i, 2] += (dp[i - 1, 1] + dp[i - 1, 2]) % MOD

    print(dp[S, 0] % MOD)


solve(S)


Measured memory_bytes: 117476
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define out(a) cout<<fixed<<setprecision((a))
 

int main(){ 
	ll a,b;
	cin >> a >> b;
	if(a>=13){
		cout << b << endl;
	}else if(a>=6){
		cout << b/2 << endl;
	}else{
		cout << 0 << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int x,a,b;
  cin>>x>>a>>b;
  x-=a;
  cout<<x%b<<endl;
  return 0;
}

Measured memory_bytes: 256
import math

n = int(input())
#a = int(input())
#d,x = list(map(int,input().split(" ")))
#ls = list(input().split(" "))
#ls = list(map(int,input().split(" ")))
#a,b,c = list(input().split())
#string = input()
#ls = [int(input()) for i in range(n)]
ls1 = [input() for i in range(n)]
m = int(input())
ls2 = [input() for i in range(m)]

ans = [0]

for i in ls1:
  ans.append(ls1.count(i) - ls2.count(i))
print(max(ans))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using s64 = signed long long;
using u64 = unsigned long long;
using f128 = long double;

int main()
{
    s64 n, k;
    cin >> n >> k;
    vector<s64> p(n), c(n);
    for(s64 i = 0; i < n; i++)
    {
        cin >> p[i];
    }
    for(s64 i = 0; i < n; i++)
    {
        cin >> c[i];
    }

    s64 maxScore = LLONG_MIN;
    for(s64 i = 0; i < n; i++)
    {
        s64 score = 0;
        s64 next = p[i] - 1;
        for(s64 j = 0; j < k; j++)
        {
            score += c[next];
            if(score > maxScore)
            {
                maxScore = score;
            }

            if(next == i)
            {
                s64 loopScore = score;
                if(loopScore > 0)
                {
                    s64 leftMoveCount = k - j - 1;
                    s64 loopLength = j + 1;
                    s64 leftLoopCount = leftMoveCount / loopLength;

                    // 完全ループ数-1まではスコアを加算できる
                    score += loopScore * (leftLoopCount - 1);

                    // (1ループ + 残りの移動回数)で最大値になるところ
                    leftMoveCount -= (leftLoopCount - 1) * loopLength;
                    next = p[i] - 1;
                    for(s64 j2 = 0; j2 < leftMoveCount; j2++)
                    {
                        score += c[next];
                        if(score > maxScore)
                        {
                            maxScore = score;
                        }
                        next = p[next] - 1;
                    }
                }

                break;
            }
            else
            {
                next = p[next] - 1;
            }
        }
    }

    cout << maxScore << endl;

    return 0;
}


Measured memory_bytes: 3612
#define NDEBUG

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <tuple>
#include <set>
#include <map>

// [0, max)
#define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var))
// [min, max)
#define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var))
// [min, max)
#define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

// a < b < c
#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
// a <= b < c
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
// a < b <= c
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))
// a <= b <= c
#define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c)))

#ifndef NDEBUG
#  define MASSERT(cond) m_assert(cond, __LINE__, #cond);
#else
#  define MASSERT(...)
#endif

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

using ld = long double;

void m_assert(const bool& cond, const sl& line, const char *condstr) {
  if (!cond) {
    cerr << "Assertion Failed: " << condstr << " at line " << line << endl;
    exit(1);
  }
}

static sl N;
static vector<sl> Bi;

void solve(void) {
  vector<sl> Ai(N);
  Ai[0] = Bi[0];
  FOR0(i, N - 2) {
    Ai[i + 1] = min(Bi[i], Bi[i + 1]);
  }
  Ai[N - 1] = Bi[N - 2];
  cout << accumulate(begin(Ai), end(Ai), 0) << endl;
}

int main(void) {
  cin >> N;
  Bi.resize(N - 1, 0);
  FOR0(i, N - 1) {
    cin >> Bi[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        in.nextLine();
        String s=in.nextLine();
        int len=s.length();
        char ch[]=s.toCharArray();
        String s1="";
        String ss="...";
        if(len>n){
            for (int i = 0; i <n; i++) {
                s1=s1+ch[i];
            }
            s1=s1+ss;
            System.out.println(s1);
        }else{
            System.out.println(s);
        }
    }
}

Measured memory_bytes: 27044
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;

const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

void pushHeap(vector<int>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}

int popHeap(vector<int>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  int i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}

vector<int> ver;
void dfs(const graph &g,int v){
  ver[v]=1;
  for(auto i:g[v]){
    if(ver[i]!=1)continue;
    dfs(g,i);
  }
}

int pa,pb,pc;
int l[8];
int* last;
int mp(int a,int b,int c,int n,int* l){
  if(n==0 || l==last){
    if(pa==a || pb==b || pc==c)return MOD;
    return abs1(a)+abs1(b)+abs1(c);
  }
  int d[4];
  d[0]=mp(a,b,c,n,l+1);
  d[1]=mp(a-*l,b,c,n-1,l+1)+10;
  d[2]=mp(a,b-*l,c,n-1,l+1)+10;
  d[3]=mp(a,b,c-*l,n-1,l+1)+10;
  int ret=MOD;
  for(int i=0;i<4;i++)ret=min(ret,d[i]);
  return ret;
}

int main(){
  int i,j,k,p,cnt=0;
  int n,a,b,c;
  cin>>n>>a>>b>>c;
  pa=a;pb=b;pc=c;
  for(i=0;i<n;i++)cin>>l[i];
  last=l+n;
  cout<<mp(a,b,c,n,l)-30<<endl;
}

Measured memory_bytes: 256
# coding: utf-8

D = int(input())
C = list(map(int,input().split()))
S = []
for i in range(D):
    s = list(map(int,input().split()))
    S.append(s)
    
#S = [0] + S
day_of_problems = [0] * 27
past = []
#def cal_last(i):#満足度低下の計算
 #   if i in past:
  #      return past.index(i)
ans = 0
for i in range(D):#i+1日目
    t = int(input())
    day_of_problems[t] = i+1
    ans += S[i][t-1]
    for j in range(26):
        ans -= C[j] * (i+1-day_of_problems[j+1])
    print(ans)

Measured memory_bytes: 69708
#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

long long h, w;
string grid[1005];
long long dp[1005][1005] = {0};

long long solve();

int main() {
  cin >> h >> w;
  for(int i = 0; i < h; ++i) cin >> grid[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  for(int i = 0; i < w; ++i) {
    if(grid[0][i] == '.')
      dp[0][i] = 1;
    else
      break;
  }
  for(int i = 0; i < h; ++i) {
    if(grid[i][0] == '.')
      dp[i][0] = 1;
    else
      break;
  }
  for(int i = 1; i < h; ++i)
    for(int j = 1; j < w; ++j) {
      if(grid[i][j] == '#') continue;
      if(grid[i - 1][j] == '.') dp[i][j] += dp[i - 1][j];
      if(grid[i][j - 1] == '.') dp[i][j] += dp[i][j - 1];
      dp[i][j] %= N;
    }
  return dp[h - 1][w - 1];
}

Measured memory_bytes: 9216
# Union find
# かっつぱさんの解説と公式のスライドみた
# https://www.youtube.com/watch?time_continue=916&v=zxor0DdwoXA&feature=emb_logo
# https://www.slideshare.net/chokudai/union-find-49066733

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]

root = [-1]*n

def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def unite(x, y):
    gx = find(x)
    gy = find(y)
    
    if gx == gy:
        return
      
    if root[gx] > root[gy]:
        gx, gy = gy, gx
        
    root[gx] += root[gy]
    root[gy] = gx

def size(x):
    x = find(x)
    return -root[x]

for a, b in AB:
    a -= 1
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, size(i))
print(ans)

Measured memory_bytes: 49780
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  ll m;
  cin >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end(), greater<int>());
  int maxa = a.front();

  int cspartner[maxa*2+1] = {};
  for (int ai : a) {
    cspartner[ai]++;
  }
  for (int i = maxa*2; i > 0; i--) {
    cspartner[i-1] += cspartner[i];
  }

  int l = 2, r = maxa*2+1;
  while (l < r) {
    ll way = 0;
    int c = (l + r + 1) / 2;
    for (int ai : a) {
      way += c > ai ? cspartner[c-ai] : n;
    }
    if (way < m) r = c - 1;
    else l = c;
  }
  int x = l;

  ll cshappy[n+1] = {};
  for (int i = 0; i < n; i++) {
    cshappy[i+1] = cshappy[i] + a[i];
  }

  ll ans = 0, way = 0;
  for (int ai : a) {
    if (x > ai) {
      int partner = cspartner[x-ai];
      ans += 1LL*ai*partner + cshappy[partner];
      way += partner;
    }
    else {
      ans += 1LL*ai*n + cshappy[n];
      way += n;
    }
  }

  if (way > m) {
    ans -= (way - m) * x;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2176
import itertools
n,m = map(int,input().split())
ways = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    ways[a-1].append(b-1)
    ways[b-1].append(a-1)
checklist = [0]*n
position = 0 #first position
cnt = 0
if n == 2:
    if 1 in ways[0]:
        print(1)
    else:
        print(0)
    exit()
for p in itertools.permutations(range(1,n)):
    if p[0] in ways[0]:
        flag = True
        for i in range(n-2):
            if p[i+1] not in ways[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)


Measured memory_bytes: 3064
//Coded by Dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
int n;
bool pd;
int main() {
	scanf("%d", &n);
	for(re int i = 1; i <= 9; ++i) {
		if(n % i == 0 && n / i <= 9) {
			pd = 1;
			break;
		}
	}
	if(pd)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define all(x) (x).begin(),(x).end()

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);std::cout<<std::fixed<<std::setprecision(10);
    ll N,K;
    cin >> N >> K;
    ll key = 1;
    key = (K*(K-1)/2) % mod;
    vector<int> A(N);
    REP(i,N)cin >> A[i];
    vector<int> B(N),C(N);
    REP(i,N){
        REP(l,N)if(A[i] < A[l]){
            B[i] ++;
            if(i>l)C[i]++;
        }
    }
    ll ans = 0;
    REP(i,N)ans = (ans + B[i] * key + C[i] * K)%mod;
    cout <<ans<< "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_N 1000
#define INF 1000000000
int dist[MAX_N], color[MAX_N]; vector<pair<int, int> >X[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >Q;
long long prim(int V) {
	for (int i = 0; i < V; i++) { dist[i] = INF; color[i] = WHITE; }
	dist[0] = 0; color[0] = GRAY; Q.push(make_pair(0, 0));
	while (!Q.empty()) {
		pair<int, int>pa = Q.top(); Q.pop();
		int a1 = pa.first, a2 = pa.second; color[a2] = BLACK;
		for (int i = 0; i < X[a2].size(); i++) {
			int to = X[a2][i].first, leng = X[a2][i].second;
			if (dist[to] > leng && color[to] < BLACK) {
				dist[to] = leng; Q.push(make_pair(dist[to], to));
			}
		}
	}
	long long sum = 0; for (int i = 0; i < V; i++) { sum += dist[i]; }//0-indexed
	return sum;
}
int main() {
	int N, M, a, b, c;
	while (true) {
		for (int i = 0; i < MAX_N; i++) { X[i].clear(); }
		cin >> N >> M; if (N == 0 && M == 0) { break; }
		for (int i = 0; i < M; i++) {
			cin >> a >> b >> c; X[a].push_back(make_pair(b, c));
			X[b].push_back(make_pair(a, c));
		}
		cout << prim(N) << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
N, M = map(int,input().split())

def factorical(n):
  ret = 1
  for i in range(1,n+1):
    ret *= i
    ret %= 10**9+7
  return ret

diff = abs(N - M)
max_ = int(1e9+7)

if(diff >= 2):
  print(0)
elif(diff == 1):
  n = N % max_
  m = M % max_
  print((factorical(n)*factorical(m)) % max_)
else:
  n = N % max_
  m = M % max_
  print((2*factorical(n)*factorical(m)) % max_)


Measured memory_bytes: 3064
#encoding:utf-8
numbers = []

while gets
 numbers.push $_.to_i
end

def count_pattern integer
 count = 0
 a = 0
 while a < 10
  b = 0
  while b < 10
   c = 0
   while c < 10
    d = 0
    while d < 10
     if a + b + c + d == integer
      count += 1
     end
     d += 1
    end
    c += 1
   end
   b += 1
  end
  a += 1
 end
 puts count
end

i = 0
while i < numbers.length
 count_pattern numbers[i]
 i += 1
end

Measured memory_bytes: 6100
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll ind[105];
vector<pair<string,ll>> v(105);
bool comp(ll a,ll b){
    if(v[a].first<v[b].first||(v[a].first==v[b].first&&v[a].second>v[b].second))
    return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
        ind[i]=i;
    }
    sort(ind,ind+n,comp);
    for(ll i=0;i<n;i++)
    cout<<ind[i]+1<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
  int N;
  cin >> N;
  
  int P[N];
  int Q[N];
  
  for (int i = 0; i < N; i++) {
    cin >> P[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> Q[i];
  }
  
  vector<int> nums;
  for (int i = 1; i <= N; i++) {
    nums.push_back(i);
  }
  
  int posP, posQ = -1;
  int pos = 1;
  do{
    bool equalP = true;
    for(int i=0;i<N;i++){
      if(P[i] != nums[i]) {
        equalP = false;
      }
    }
    if (equalP) posP = pos;

    bool equalQ = true;
    for(int i=0;i<N;i++){
      if(Q[i] != nums[i]) {
        equalQ = false;
      }
    }
    if (equalQ) posQ = pos;

    pos++;
  }while(next_permutation(nums.begin(),nums.end()));
  
  cout << abs(posP-posQ) << endl;
  
}


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

const int MAXN = 1005;
const int MAXV = MAXN*MAXN/2;
vector<int> to[MAXV];
int id[MAXN][MAXN];

//とりあえず、試合のIDを返す関数を作成。
int toId(int i,int j){
    if(i > j) swap(i,j);
    return id[i][j];
}

bool visited[MAXV];//こっちは履歴.
bool calculated[MAXV];//ループ検出用
int dp[MAXV];//vからスタートしたときの最大経路をここにセット.
int dfs(int v){
    if(visited[v]){
        if(!calculated[v])return -1;
        return dp[v];
    }
    visited[v] = true;
    dp[v] = 1;
    //vから始まる頂点を全て見る.
    for(int u:to[v]){
        int res = dfs(u);
        if(res == -1)return -1;
        dp[v] = max(dp[v],res+1);
    }
    calculated[v] = true;
    return dp[v];
}

int main(){
    //方針1
    int n;cin>>n;
    vector<vector<int>> a(n,vector<int>(n-1));
    rep(i,n){
        rep(j,n-1){
            cin>>a[i][j];
            a[i][j]--;
        }
    }
    //id割り振り.
    int V = 0;
    rep(i,n)rep(j,n){
        if(i < j){
            id[i][j] = V++;
        }
    }
    //頂点間の辺を張っていく。
    rep(i,n){
        rep(j,n-1){
            //頂点番号に変換.
            a[i][j] = toId(i,a[i][j]);
        }
        rep(j,n-2){
            to[a[i][j+1]].push_back(a[i][j]);
            //逆向きに辺を張る.
        }
    }
    //ここまででグラフは完成.
    //好きな位置からdfsをする.
    int ans = 0;
    rep(i,V){
        int res = dfs(i);
        if(res == -1){
            puts("-1");
            return 0;
        }
        ans = max(ans,res);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 38528
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

using namespace std;

int main(){
	int X,A;
	cin >> X >> A;
	cout << ((X<A) ? "0":"10") << endl;
}


Measured memory_bytes: 256
n = int(input())
xi = [int(x) for x in input().split()]
yi = [int(y) for y in input().split()]
ans1 = ans2 = ans3 = ansm = 0
for i in range(n):
    sa = abs(xi[i]-yi[i])
    ans1 += sa
    ans2 += sa**2
    ans3 += sa**3
    if ansm < sa:
        ansm = sa
print(ans1,ans2**(1/2),ans3**(1/3),ansm, end='\n')


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

#define For(i,a,b) for(int (i) = (a);(i) < (b);i++)
#define Rep(i,n) For((i),0,(n))
#define All(a) (a).begin(),(a).end()
#define sp " "
#define INF 1e18
#define INT_INF 1e9
#define MAX 1000

typedef long long ll;

int main(){
    string S;
    int N;
    cin >> S;
    N = S.size();
    vector<ll> ans(N+1,-1);
    ll res = 0;
    S = '>' + S;
    S = S + '<';
    Rep(i,N+1){
        if(S[i] == '>' && S[i+1] == '<'){
            ans[i] = 0;
        }
    }
    Rep(i,N+1){
        if(ans[i] == 0){
            int j = i;
            while(S[j+1] == '<' && j < N){
                ans[j+1] = max(ans[j] + 1,ans[j+1]);
                //cout << j+1 << sp << ans[j+1] << endl;
                j++; 
            }
            j = i;
            while(S[j] == '>' && j > 0){
                ans[j-1] = max(ans[j] + 1,ans[j-1]);
                j--;
            }
        }
    }
    Rep(i,N+1){
        //cout << ans[i] << sp;
        res += ans[i];
    }
    cout << res << endl;
    //cin >> N;
}

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

using namespace std;
typedef long long int ll;

int dh[4] = {1,0,-1,0};
int dw[4] = {0,1,0,-1};

int main()
{
   int N,W;
   cin >> N >> W;
   vector<int>v(N),w(N);
   for(int i = 0; i < N; i++) cin >> v[i] >> w[i];
   vector<vector<int>>dp(N+1,vector<int>(W+1,0));
   for(int i = 0; i <= W; i++) dp[0][i] = 0;
   for(int i = 0; i < N; i++)
   {
       for(int j = 0; j <= W; j++)
       {
           if(j - w[i] >= 0) dp[i+1][j] = max(dp[i+1][j-w[i]] + v[i],max(dp[i][j-w[i]] + v[i],dp[i][j]));
           else dp[i+1][j] = dp[i][j];
       }
   }
   cout << dp[N][W] << endl;
}


Measured memory_bytes: 6780
function Main(input) {
  lines = input.split('\n')
  line = lines[0].split(' ')
  n = parseInt(line[0])
  m = parseInt(line[1])
  if (n < 10 && m < 10) {
    console.log(n * m)
  } else {
    console.log(-1)
  }
}

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

Measured memory_bytes: 11468
def main():
    mat = []
    for _ in range(3):
        mat.append([int(c) for c in input().split()])
    for j in range(2):
        ref = mat[0][j+1] - mat[0][j]
        if ref != mat[1][j+1] - mat[1][j] or ref != mat[2][j+1] - mat[2][j]:
            return "No"
    for i in range(2):
        ref = mat[i+1][0] - mat[i][0]
        if ref != mat[i+1][1] - mat[i][1] or ref != mat[i+1][2] - mat[i][2]:
            return "No"
    return "Yes"


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

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

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a+b > c+d){
        cout<<"Left";
        return 0;
    }
    else if(a+b < c+d){
        cout<<"Right";
        return 0;
    }
    else{
        cout<<"Balanced";
        return 0;
    }
    return 0;
}


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

int main()
{
    int a[33]={0,1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
    int k;
    scanf("%d",&k);
    printf("%d",a[k]);
    return 0;
}

Measured memory_bytes: 128
package main

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

var stdin = bufio.NewScanner(os.Stdin)
var inc = map[bool]int{true: 1, false: 0}

func main() {
	arr := scanArrayInt()
	h, w := arr[0], arr[1]
	grids := [][]interface{}{}
	for i := 0; i < h; i++ {
		stdin.Scan()
		in := []interface{}{}
		for _, v := range strings.Split(stdin.Text(), "") {
			in = append(in, v)
		}
		grids = append(grids, in)
	}
	//{x,y}
	dxy := [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if grids[i][j] == "#" {
				continue
			}
			c := 0
			for _, vs := range dxy {
				dx, dy := vs[0], vs[1]
				if j+dx < 0 || j+dx > w-1 || i+dy < 0 || i+dy > h-1 {
					continue
				}
				if grids[i+dy][j+dx] == "#" {
					c++
				}
			}
			grids[i][j] = c
		}
	}
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			fmt.Print(grids[i][j])
		}
		fmt.Print("\n")
	}
}
func scanArrayInt() []int {
	var ret = []int{}
	stdin.Scan()
	for _, s := range strings.Split(stdin.Text(), " ") {
		i, _ := strconv.Atoi(s)
		ret = append(ret, i)
	}
	return ret
}

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        cin >> h.at(i);
    }
    int count = 0;
    int maxnum = 0;
    for(int i = 0; i < n-1; i++){
        if(h.at(i) >= h.at(i+1)){
            count++;
        } else {
            maxnum = max(count, maxnum);
            count = 0;
        }
    }
    maxnum = max(count, maxnum);
    cout << maxnum << endl;
}

Measured memory_bytes: 640
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const A = arg[1].split(" ").map(n=>parseInt(n));
    
    let answer = 0;
    let free = 0;
    let colors = [0, 0, 0, 0, 0, 0, 0, 0];
    
    for(let i in A) {
        if(A[i] < 400) {
            colors[0]++;
        } else if(A[i] < 800) {
            colors[1]++;
        } else if(A[i] < 1200) {
            colors[2]++;
        } else if(A[i] < 1600) {
            colors[3]++;
        } else if(A[i] < 2000) {
            colors[4]++;
        } else if(A[i] < 2400) {
            colors[5]++;
        } else if(A[i] < 2800) {
            colors[6]++;
        } else if(A[i] < 3200) {
            colors[7]++;
        } else {
            free++;
        }
    }
    
    answer += colors.filter(n=>n !== 0).length;
    
    console.log(Math.max(1, answer) + " " + (answer + free));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int n,k,ans;
int a[200010];

int main()
{
	scanf("%d%d",&k,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	ans=a[2]-a[1];
	for(int i=2;i<n;i++) ans=max(ans,a[i+1]-a[i]);
	ans=max(ans,a[1]+k-a[n]);
	printf("%d\n",k-ans);
	return 0;
}

Measured memory_bytes: 4612
/*
 It's better to sleep happy and tired rather than disappointed and frustrated
 There's only 1 thing that's impossible and that is defeating a man who doesn't give up
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mx2 102
#define mx3 1003
#define mx4 10004
#define mx5 100005
#define mx6 1000006
#define mod 1000000007
#define PI 3.14159265
#define deb(x) cout << #x << " " << x << endl;
#define fo(i,n) for(int i=0 ; i<n ; i++)
#define Fo(i,k,n) for(int i=k ; i<n ; i++)
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pair<int,int>,int> piii;

const int inf=0x3f3f3f3f;
int n , ans , sum , a , b ,arr[mx5];
ll dp[3000][3000][2];
string str;

ll solve(int l ,  int r,int t)
{
	if(r-l<0)
	{
		return 0;
	}
	if(dp[l][r][t]!=-1)
	{
		return dp[l][r][t];
	}
	dp[l][r][t]=(t==0? max(solve(l+1,r,1)+arr[l] , solve(l,r-1,1)+arr[r]) : min(solve(l+1,r,0)-arr[l] , solve(l,r-1,0)-arr[r]));
	// cout<<l<<" "<<r<<" "<<t <<" " << dp[l][r][t]<<"\n";
	return dp[l][r][t];
}

int main() {
	ios::sync_with_stdio(false);
	//int t;cin>>t;while(t--)
	{
		cin>>n;
		fo(i,n)cin>>arr[i];
		memset(dp,-1,sizeof(dp));
		cout<<solve(0,n-1,0);
	}
	return 0;
}


Measured memory_bytes: 141056
#include <iostream>
#include <cstdint>

using namespace std;

int possible(int msd, int lsd, int max) {
  int result = 0;
  for (int i = 1; i <= max; ++i) {
    if (i % 10 != lsd) continue;
    int here = i;
    while (here >= 10) here /= 10;
    if (here != msd) continue;
    ++result;
  }
  return result;
}

int main(void) {
  int n;
  cin >> n;

  uint64_t passed = 0;
  for (int am = 1; am <= 9; ++am) {
    for (int al = 1; al <= 9; ++al) {
      // 二桁以上
      passed += possible(am, al, n) * possible(al, am, n);
    }
  }

  cout << passed << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
class Main {
    public static void main(String[] args) {
      
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
      	int C = sc.nextInt();
      
      if(A+B+1>=C){System.out.print(B+C);}
      else{System.out.print(B*2+A+1);}
 
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string j;
    cin>>j;
    int c = 0;
    for(int i=0;j[i]!='\0';i++)
    {
        if(j[i]=='A')
        {
            if((j[i+1] == 'B')&&(j[i+2]=='C'))
            {
                c++;
                i = i+2;

            }
            
        }
    }
    cout<<c;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int[] ai = new int[N];

   for (int i = 0;i<N;i++) ai[i] = sc.nextInt();
   int ans = 0;
   
   int brick = 1; 
   for(int i = 0;i<N;i++)
   {
     if(ai[i]==brick) brick++;
     else ans++;
   }
   if(ans==N&&brick==1) ans = -1;
   System.out.println(ans);
 }
}

Measured memory_bytes: 65536
#include <iostream>
#include <algorithm>

int main() {
    using namespace std;

    int N;
    cin >> N;

    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
#include <bits/stdc++.h>

int main() {
    long long n;
    std::cin >> n;
    std::map<long long, long long> cnt, cnt2;
    for (int i = 0; i < n; i++) {
        long long t;
        std::cin >> t;
        if (i % 2) cnt[t]++;
        else cnt2[t]++;
    }
    auto m = 0ll, m2 = 0ll, s = 0ll, s2 = 0ll;
    for (auto& el : cnt) {
        if (el.second > cnt[m]) {
            s = m;
            m = el.first;
        } else if (el.second > cnt[s]) {
            s = el.first;
        }
    }
    for (auto& el : cnt2) {
        if (el.second > cnt2[m2]) {
            s2 = m2;
            m2 = el.first;
        } else if (el.second > cnt2[s2]) {
            s2 = el.first;
        }
    }

    if (m != m2) {
        std::cout << n - cnt[m] - cnt2[m2] << std::endl;
    } else {
        std::cout << n - std::max(cnt[m] + cnt2[s2], cnt[s] + cnt2[m2]) << std::endl;
    }

    return 0;
}


Measured memory_bytes: 6528
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;

//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2005;
const int INF = 1e9 + 5;

int n, m, q, up[N][N], lf[N][N], cnt[N][N];
char a[N][N];

int SumCnt(int x1, int y1, int x2, int y2) {
	return cnt[x2][y2] - cnt[x2][y1 - 1] - cnt[x1 - 1][y2] + cnt[x1 - 1][y1 - 1];
}

int SumUp(int x1, int y1, int x2, int y2) {
	++x1;
	if(x1 > x2) return 0;
	return up[x2][y2] - up[x2][y1 - 1] - up[x1 - 1][y2] + up[x1 - 1][y1 - 1];
}

int SumLeft(int x1, int y1, int x2, int y2) {
	++y1;
	if(y1 > y2) return 0;
	return lf[x2][y2] - lf[x2][y1 - 1] - lf[x1 - 1][y2] + lf[x1 - 1][y1 - 1];
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	for(int i = 2; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			up[i][j] = up[i][j - 1] + up[i - 1][j] - up[i - 1][j - 1];
			if(a[i][j] == '1' && a[i - 1][j] == a[i][j]) {
				++up[i][j];
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 2; j <= m; ++j) {
			lf[i][j] = lf[i][j - 1] + lf[i - 1][j] - lf[i - 1][j - 1];
			if(a[i][j] == '1' && a[i][j - 1] == a[i][j]) {
				++lf[i][j];
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cnt[i][j] = cnt[i][j - 1] + cnt[i - 1][j] - cnt[i - 1][j - 1];
			if(a[i][j] == '1') {
				++cnt[i][j];
			}
		}
	}
	for(int i = 1; i <= q; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << SumCnt(x1, y1, x2, y2) - SumLeft(x1, y1, x2, y2) - SumUp(x1, y1, x2, y2) <<'\n'; 
	}
	return 0;
}
/*
	If you only do what you can do, 
	You will never be more than you are now!
*/

Measured memory_bytes: 52864
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;


int main()
{
    IOS
    ll n;
    cin>>n;
    ll ans=(n*(n+1))/2;
    ans-=n;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

fun main(args: Array<String>) = test2()

fun test2() = FastIO().exec {
    val (k, n) = readLine()!!.split(' ').map { it.toInt() }
    val aList = readLine()!!.split(' ').map { it.toLong() }

    val diff = LongArray(n)
    diff[0] = k - aList.last() + aList.first()

    for (i in 0 until n - 1) {
        diff[i + 1] = aList[i + 1] - aList[i]
    }

    val answer = diff.sum() - diff.max()!!

    println(answer)
}

// region

@Suppress("unused")
class FastIO {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var st = StringTokenizer("")
    val pw = PrintWriter(System.out)

    fun string(): String {
        if (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())
        return st.nextToken()
    }

    fun int() = Integer.parseInt(string())
    fun long() = java.lang.Long.parseLong(string())
    fun double() = java.lang.Double.parseDouble(string())
    fun nextLine() = br.readLine()!!
    fun println() = pw.println()
    fun <T> print(o: T) = pw.print(o)
    fun <T> println(o: T) = pw.println(o)

    inline fun exec(code: FastIO.() -> Unit) {
        code()
        pw.flush()
    }
}
// endregion


Measured memory_bytes: 81088
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
a1 = a[:n // 2]
a2 = a[n // 2:]
if n % 2 == 0:
    print(sum(a2) * 2 - min(a2) - sum(a1) * 2 + max(a1))
else:
    print(max(sum(a2) * 2 - a2[0] - a2[1] - sum(a1) * 2, (sum(a2) -a2[0]) * 2 - (sum(a1) + a2[0]) * 2 + a2[0] + max(a1)))


Measured memory_bytes: 7764
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(){

	int n,p;
	while(cin >> n >> p && !(n == 0 && p == 0)){
		int wan=0;
		int cand[50];
		int tern = 0;
		wan = p;
		fill(cand,cand+50,0);
		while(1){
			if(wan==0){
				wan += cand[tern];
				cand[tern]=0;
			}
			else{
				wan--;
				cand[tern]++;
				if(cand[tern] == p)
					break;
			}
			tern = (tern + 1) % n;
		}
		cout << tern << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
#define pii pair<int,int>
#pragma GCC optimize("Ofast")
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define isSquare(x) (sqrt(x)*sqrt(x) == x)
template<class T>bool chmax(T &a, const T &b) {if(a<b){a = b; return 1;} return 0; };
template<class T>bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };
inline void IN(void){return;}
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
inline void OUT(void){cout << "\n";return;}
template <typename First, typename... Rest> void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}
const double EPS = 1e-9;
const int mod = 1e9 + 7;
const int INF = 1e9;
const long long LLINF = 1e18;
long long lcm(ll a, ll b){return a * b / __gcd(a,b);}
struct IoSetup { IoSetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
} } iosetup;
template< int mod > struct ModInt {
    int x; ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }return ModInt(u);}
    ModInt pow(int64_t n) const {ModInt ret(1), mul(x); while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); }
    static int get_mod() { return mod; }
}; using modint = ModInt< mod >;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int dis(int k){
    int res = 0;
    while(k > 0){
        res += k%10;
        k /= 10;
    }
    return res;
}

int main(){
    iosetup;
    int N; IN(N);
    int ans = INF;
    rep(i, 1, N){
        chmin(ans, dis(i) + dis(N - i));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(i+1==a[i]){
      if(i<n-1&&a[i+1]==i+2)a[i+1]=a[i];
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640