akhauriyash/Code-Regression huggingface dataset:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from collections import deque

import queue

def get_ind(pre_tuple, num):
    a, b = pre_tuple
    ans = (a - 1) * num + b
    return ans



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    graph_data = [set() for i in range(num * num)]
    parent_node = [0 for i in range(num * num)]

    for i in range(num):
        now_node = i + 1
        pre_tuple = (0, 0)
        for j in range(num - 1):
            next_node = data[i][j]
            now_tuple = (min(now_node, next_node), max(now_node, next_node))
            if j == 0:
                pass
                # parent_node[now_tuple] += 0
            else:
                index = get_ind(pre_tuple, num)
                # print(index, pre_tuple)
                graph_data[index].add(now_tuple)
                index2 = get_ind(now_tuple, num)
                parent_node[index2] += 1
            pre_tuple = now_tuple

    q = deque([])
    count_node, ans = 0, 0

    for i in range(1, num + 1):
        for j in range(i + 1, num + 1):
            node = (i, j)
            index = get_ind(node, num)
            if parent_node[index] == 0:
                q.append((node, 1))
                count_node += 1

    ans = 0
    while len(q) > 0:
        now_node, length = q.popleft()
        ans = max(ans, length)
        index = get_ind(now_node, num)
        for next_node in graph_data[index]:
            index2 = get_ind(next_node, num)
            parent_node[index2] -= 1
            if parent_node[index2] == 0:
                q.append((next_node, length + 1))
                count_node += 1

    if count_node < (num * (num - 1)) // 2:
        print(-1)
    else:
        print(ans)







if __name__ == '__main__':
    main()



Measured memory_bytes: 205900
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	bool e,f,g;
	if(a<b){
		if(b-a<=d)e=true;
		else e=false;
	}
	else if(a-b<=d)e=true;
	      else e=false;
	if(b<c){
		if(c-b<=d)f=true;
		else f=false;
	}
	else if(b-c<=d)f=true;
	      else f=false;
	if(a<c){
		if(c-a<=d)g=true;
		else g=false;
	}
	else if(a-c<=d)g=true;
	      else g=false;
	 if(e==true&&f==true)cout<<"Yes"<<endl;
	 else if(g==true)cout<<"Yes"<<endl;
	 else cout<<"No"<<endl;
	return 0;
	}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5 + 5;

int a[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    int mn = 2e9;
    for(int i = k-1; i < n; i++){
        mn = min(mn, a[i] - a[i - k + 1]);
    }
    cout << mn;

    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
//#include<string.h>
int main(){
    char a[200001];
    char b[200001];
    scanf("%s",a);
    scanf("%s",b);
    int n=0;
    while(a[n]!='\0'){
        n++;
    }
    int count=0;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i])
        count++;
    }
    printf("%d",count);
    return 0;

}


Measured memory_bytes: 2076
var
	N,i,j,ans:int64;
begin
	read(N);
	i:=1;
	while i<=N do begin
		j:=N div(N div i)+1;
		inc(ans,(j-i)*(i+j-1)*(N div i)*(N div i+1)div 4);
		i:=j;
	end;
	writeln(ans);
end.

Measured memory_bytes: 1340
import sys

def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for (w, _s, _t), _ in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n-1)):
        cost += w
    return cost

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


Measured memory_bytes: 24008
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<stack>
#include<climits>
#include<cmath>

using namespace std;

#define int long long
#define MOD (1000000007)
#define MINF (-1*(LLONG_MAX-10))
#define INF (LLONG_MAX-10)

signed main(){
    int N,M;
    cin>>N>>M;

    if(N==M) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
   int i,j,r,c;
   scanf("%d %d",&r,&c);
   int shet[(r+1)][(c+1)];
   for(i=0;i<=r;i++){
	   for(j=0;j<=c;j++){
		   shet[i][j]=0;
	   }
   }
   for(i=0;i<r;i++){
         for(j=0;j<c;j++){
               scanf("%d",&shet[i][j]);
               shet[r][j]=shet[r][j]+shet[i][j];
               shet[i][c]=shet[i][c]+shet[i][j];
         }
         shet[r][c]=shet[r][c]+shet[i][c];
   }
   for(i=0;i<=r;i++){
      for(j=0;j<=c;j++){
         printf("%d",shet[i][j]);
         if(j!=c) printf(" ");
      }
      printf("\n");
   }
   return 0;
}

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

int main() {
    char x, y;
    cin >> x >> y;
    char answer = 0;
    if(x > y){
        answer = '>';
    } else if(x < y){
        answer = '<';
    } else if(x == y){
        answer = '=';
    }
    cout << answer << endl;
}

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

int t;
long long a, b, c, d, e, f, g;

signed main () {
	scanf("%d", &t);
	while (t--) {
		scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
		if (b > a || b > d)
			printf("No\n");
		else if (c >= b)
			printf("Yes\n");
		else {
			e = a % b;
			g = __gcd(b, d);
			f = ((c - e + g) / g) * g;
			if (c < e || f + e < b)
				printf("No\n");
			else
				printf("Yes\n");
		}
	}
}


Measured memory_bytes: 3644
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
        int max_x = x, min_y = y;
        for (int i = 0; i < n; i++) max_x = Math.max(max_x, sc.nextInt());
        for (int i = 0; i < m; i++) min_y = Math.min(min_y, sc.nextInt());
        System.out.println(max_x < min_y ? "No War": "War");
    }
}

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

int main () {
  long long x,k,d;
  cin >> x >> k >> d;
  long long ans,m;
  x=labs(x);
  m=floor(x/d);
  if(m>k) ans=x-k*d;
  else if((m%2)==(k%2)) ans=x%d;
  else ans=d-(x%d);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3584
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define RG register
#define IL inline
#define LL long long
#define inf 2147483640
#define pi acos(-1.0)
#define N 100005
using namespace std;
IL int gi()
{
	RG char ch;RG int s=1,res=0;
	for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
	if(ch=='-') s=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) res=10*res+ch-48;
	return res*s;
}
int n,a[N]={0};
int sum1=0,sum2=0,sum3=0;
int main()
{
	//freopen("c.in","r",stdin);
	//freopen("c.out","w",stdout);
	n=gi();
	for(RG int i=1;i<=n;++i) a[i]=gi();
	for(RG int i=1;i<=n;++i)
		{
			if(a[i]&1) sum3+=1;
			else if( !( a[i]%4) ) sum1+=1;
			else sum2+=1;
		}
	if((sum3-1)>sum1) printf("No\n");
	else if(sum3-1<sum1) printf("Yes\n");
	else
		{
			if(sum2) printf("No\n");
			else printf("Yes\n");
		}
	//fclose(stdin);fclose(stdout);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))
#define DEBUG 0

string solve()
{
    ll ans = 0;
    ll N,K;
    string S;
    cin >> N >> K;
    cin >> S;
    S[K-1] += 'a'-'A';

    return S;
}

int main()
{
    do {
        cout << solve() << endl;
    } while (DEBUG);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N,K;
  cin>>N>>K;
  ll ans=K;
  for(ll i=0;i<N-1;i++) {
ans*=(K-1);
  }
  cout<<ans<<endl;
}
  

Measured memory_bytes: 3616
N = int(input())
A = list(map(int,input().split()))

A = sorted(A)

ans = 1

cum = [0]*N
for i, a in enumerate(A) :
    if i == 0 :
        cum[i] = a
    
    else :
        cum[i] = cum[i-1] + a

for i in range(N-2,-1,-1) :
    if cum[i]*2 >= A[i+1] :
        ans += 1
    else :
        break
print(ans)


Measured memory_bytes: 14320
package main

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

// D
var (
	D int
	c [26]int
	s [][26]int
)

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	defer flush()

	D = readInt()
	for i := 0; i < 26; i++ {
		c[i] = readInt()
	}
	s = make([][26]int, D)
	for d := 0; d < D; d++ {
		for i := 0; i < 26; i++ {
			s[d][i] = readInt()
		}
	}

	t := make([]int, D)
	for d := 0; d < D; d++ {
		t[d] = readInt() - 1
	}

	last := make([]int, 26)
	S := 0
	for i := 0; i < 26; i++ {
		last[i] = -1
	}
	for d := 0; d < len(t); d++ {
		S += s[d][t[d]]
		last[t[d]] = d
		for i := 0; i < 26; i++ {
			S -= c[i] * (d - last[i])
		}
		println(S)
	}
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}


Measured memory_bytes: 1996
#include "bits/stdc++.h"
using namespace std;

int main(){
int a,b,k;
cin >> a >>b >>k;
if(a+k<=b-k){
    vector<int>che(k*2);
    for(int i=0;i<k;i++){
        che.at(i)=i+a;
    }
    int i=k*2-1;
    while(i>k*2-k-1){
        che.at(i)=b;
        b--;
        i--;
    }
    sort(che.begin(),che.end());
    for(int i=0;i<k*2;i++){
        cout <<che.at(i)<<endl;
    }
}
else{
    for(int i=0;i<b-a+1;i++){
        cout << i+a<<endl;
    }
}
}

Measured memory_bytes: 256
import java.util.*;
import java.awt.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        String s=sc.next();
        String t=sc.next();
        int[] x=new int[114514];
        int[] y=new int[114514];
        int stop=s.length();
        for (int i = 0; i < stop; i++) {
            int p=s.charAt(i);
            int q=t.charAt(i);
            if(x[p]==0){
                x[p]=q;
            }else if(x[p]!=q){
                out.println("No");
                exit(0);
            }
            if(y[q]==0){
                y[q]=p;
            }else if(y[q]!=p){
                out.println("No");
                exit(0);
            }
        }
        out.println("Yes");
    }
    //階乗
static long fact(long a){
    long b=1;
    for (long i = 1; i <= a; i++) {
        b*=i;
    }
    return b;
}
//最大公約数
static int gcd (int a, int b) {
    int temp;
    while((temp = a%b)!=0) {
        a = b;
        b = temp;
    }
    return b;
}
//※最小公倍数はa*b/gcd(a,b)である
//二項係数
static long combi (long a, long b) {
    b=min(a-b,b);
    return permu(a,b)/fact(b);
}
//順列
static long permu(long a,long b){
    long temp=1;
    for (long i =a ; i > a-b; i--) {
        temp*=i;
    }
    return temp;
}
}

Measured memory_bytes: 28848
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
    int N, X;cin>>N>>X;
    vector<int> v(N+10);
    vector<int> s(N+10);
    for(int i=0;i<N;i++) cin>>v[i];
    for(int i=0;i<=N;i++){
        s[i+1] = s[i] + v[i];
    }
    int ans = 1;
    for(int i=1;i<=N;i++){
        if(s[i]>X) break;
        ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = 0

for i in range(N+1):
    cost += abs(A[i] - A[i+1])

for i in range(N):
    print(cost + abs(A[i] - A[i+2]) - abs(A[i] - A[i+1]) - abs(A[i+1] - A[i+2]))

Measured memory_bytes: 14048
X, N = list(map(int,input().split()))
p = list(map(int,input().split()))

v = 0
if N == 0:
    print(X)
else:
    while True:
        res = X - v
        if not res in p:
            break
        res = X + v
        if not res in p:
            break
        v += 1
    print(res)

Measured memory_bytes: 9188
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int N,M;
vector<vector<int>> cost;
vector<vector<bool>> used;
vector<vector<edge<int>>> G;

void dijkstra(int s, int t, vector<int> &dist){
  dist[s] = 0;
  priority_queue<Pi> que;
  que.push({0, s});
  while (!que.empty()){
    auto p = que.top(); que.pop();
    int d = p.first;
    int v = p.second;
    for (auto e : G[v]){
      int nv = e.to;
      int c = e.cost;
      if (d+c >= dist[nv]) continue;
      dist[nv] = d + c;
      que.push({dist[nv], nv});
    }
  }
  // s -> t の最短距離はOK
  queue<int> que2;
  que2.push(t);
  while (!que2.empty()){
    int v = que2.front(); que2.pop();
    for (auto e : G[v]){
      int nv = e.to;
      int c = e.cost;
      if (dist[nv]+c == dist[v]){
        used[v][nv] = true;
        used[nv][v] = true;
        que2.push(nv);
      }
    }
  }
}

int main() {
  cin >>N >>M;
  G.assign(N, vector<edge<int>>());
  cost.assign(N, vector<int>(N, -1));
  used.assign(N, vector<bool>(N, false));
  rep(i, M){
    int a,b,c; cin >>a >>b >>c;
    a--; b--;
    G[a].push_back({b,c});
    G[b].push_back({a,c});
    cost[a][b] = c;
    cost[b][a] = c;
  }
  for (int s=0; s<N; s++){
    for (int t=s+1; t<N; t++){
      vector<int> dist(N, 1000000000);
      dijkstra(s, t, dist);
    }
  }
  int res = 0;
  for (int i=0; i<N; i++){
    for (int j=i+1; j<N; j++){
      if (cost[i][j]>=0 && !used[i][j]) res++;
    }
  }
  cout <<res <<endl;
}

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

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

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

    int k;
    cin >> k;
    long long ans = 0;
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            for (int l = 1; l <= k; l++)
            {
                ans += gcd(i, gcd(j, l));
            }
        }
    }
    cout << ans;

    return 0;
}

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

int main(){
    int input;
    int h;
    int m;
    int s;
    cin >> input;
    h = input / 3600;
    m = input % 3600 / 60;
    s = input % 60;
    cout << h << ":" << m << ":" << s << endl;
    return 0;
}


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

using namespace std;

int A,B,X;

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>A>>B>>X;

if(A>X){
  cout<<"NO"<<endl; return 0;
}
if(A+B<X){
  cout<<"NO"<<endl; return 0;
}
  cout<<"YES"<<endl;

}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int N;
int C[50];
bool g(const long,const long);
bool f(int res,int start,long now,long usd)
{
	if(res==0)
	{
		return g(now,usd);
	}
	int a=__builtin_ctzll(now);
	int b=__builtin_ctzll(~usd);
	if(a>b&&C[b]>res)return false;
	int pre=-1;
	for(int i=start;i<N;i++)
	{
		if(usd>>i&1||C[i]>res||pre==C[i])continue;
		if(f(res-C[i],i+1,now|1LL<<i,usd|1LL<<i))return true;
		pre=C[i];
	}
	return false;
}
bool g(long now,long usd)
{
	if(usd==((1LL<<N)-1))return true;
	for(int i=0;i<N;i++)
	{
		if(now>>i&1)
		{
			if(f(C[i],i+1,now&~(1LL<<i),usd))return true;
		}
	}
	return false;
}
main()
{
	while(cin>>N,N)
	{
		for(int i=0;i<N;i++)cin>>C[i];
		sort(C,C+N);
		reverse(C,C+N);
	    cout<<(g(1,1)?"YES":"NO")<<endl;
	}
}


Measured memory_bytes: 3016
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

vvi G = vvi(10e5+100);
umap<int, int> mem = umap<int, int>();
int gans = 0;

int longest(int node, int prnt){
	if (mem.find(node) != mem.end()) return mem[node];
	int ans = 0;
	for(const int& nbhr : G[node]){
		if (nbhr == prnt) continue;
		ans = max(ans, 1 + longest(nbhr, node));
	}
	gans = max(gans, ans);
	mem[node] = ans;
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n, m; cin >> n >> m;
	rep(i, m){
		int u, v; cin >> u >> v;
		u--; v--;
		G[u].pb(v);
	}
	rep(i, n){
		longest(i, -1);
	}
	cout << gans;
}

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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <math.h>

int main() {

    long long int a, b;
    cin >> a >> b;

    cout << a * b << endl;

    return 0;

}


Measured memory_bytes: 3596
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 2005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

char mp[maxn][maxn];
int a1[maxn][maxn],x1[maxn][maxn],x2[maxn][maxn],n,m,Q;

inline int q(int a,int b,int c,int d,int opt)
{
	if(opt==1) return a1[c][d]-a1[a-1][d]-a1[c][b-1]+a1[a-1][b-1];
	int tmp=x1[c][d]-x1[a][d]-x1[c][b-1]+x1[a][b-1];
	return tmp+x2[c][d]-x2[a-1][d]-x2[c][b]+x2[a-1][b];
}

int main()
{
	n=read(); m=read(); Q=read();
	rep(i,1,n)
	{
		scanf("%s",mp[i]+1);
		rep(j,1,m)
		{
			a1[i][j]=a1[i][j-1]+a1[i-1][j]-a1[i-1][j-1]+(mp[i][j]=='1');
			if(mp[i][j]=='1')
			{
				x1[i][j]=x1[i][j-1]+x1[i-1][j]-x1[i-1][j-1]+(mp[i-1][j]=='1');
				x2[i][j]=x2[i][j-1]+x2[i-1][j]-x2[i-1][j-1]+(mp[i][j-1]=='1');
			}
			else
			{
				x1[i][j]=x1[i][j-1]+x1[i-1][j]-x1[i-1][j-1];
				x2[i][j]=x2[i][j-1]+x2[i-1][j]-x2[i-1][j-1];
			}
		}
	}
	
	while(Q--)
	{
		int a=read(),b=read(),c=read(),d=read();
		printf("%d\n",q(a,b,c,d,1)-q(a,b,c,d,2));
	}
	return 0;
}

Measured memory_bytes: 54756
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
typedef long long ll;
const int N = 1e5+10;

int main()
{
    int n;
    cin>>n;
    int l = n / 100;
    int r = n % 100;
    if(1<=l && l <= 12)
    {
        if(1<= r && r <= 12)
        {
            cout<<"AMBIGUOUS"<<endl;
        }
        else
        {
            cout<<"MMYY"<<endl;
        }
    }
    else
    {
        if(1<=r && r <= 12)
        {
            cout<<"YYMM"<<endl;
        }
        else
        {
            cout<<"NA"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
#include <unordered_map>
#include <vector>
#include <unordered_map>
using namespace std;

const int N = 2e5 + 7;

long long min_x[N], min_y[N];

int main() {
    long long n, q;
    scanf("%lld %lld", &n, &q);
    int xx = n, yy = n;
    for (int i = 1; i <= n; ++i) {
        min_x[i] = n;
        min_y[i] = n;
    }
    long long sum = 0;
    for (int t = 0; t < q; ++t) {
        int op, x;
        scanf("%d %d", &op, &x);
        if (op == 1) {
            if (x < xx) {
                sum += yy - 2;
                for (int i = x; i <= xx; ++i) {
                    min_x[i] = yy;
                }
                xx = x;
            } else {
                sum += min_x[x] - 2;
            }
        } else {
            if (x < yy) {
                sum += xx - 2;
                for (int i = x; i <= yy; ++i) {
                    min_y[i] = xx;
                }
                yy = x;
            } else {
                sum += min_y[x] - 2;
            }
        }
    }
    cout << (n - 2) * (n - 2) - sum << endl;
}

Measured memory_bytes: 6796
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <sstream>
#include <math.h>

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

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define SORT(c) sort((c).begin(),(c).end())
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define WARU 1000000007;

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

int main() {
	int a, b;
	cin >> a >> b;

	rep(i, 2000001) {
		if( abs(i - 1000000 - b) < a )
		cout << i - 1000000 << " ";

	}
	cout << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
        int w;
        int ans[10];

        while (cin >> w) {
                int cnt = 0;
                for (int i = 1; w; i*=2) {
                        if (w % 2) {
                                ans[cnt++] = i;
                        }
                        w /= 2;
                }
                for (int i = 0; i < cnt; i++) {
                        cout << ans[i];
                        if (i < cnt - 1) {
                                cout << " ";
                        }
                }
                cout << endl;
        }

        return 0;
}

Measured memory_bytes: 2960
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)


# 答えが負の場合
if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2

        or_higher_cnt = 0
        r = positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

# 答えが正の場合
else:
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

Measured memory_bytes: 95108
#059-C
import copy
n=int(input())
a=list(map(int,input().split()))
a1=copy.deepcopy(a)
a2=copy.deepcopy(a)
def pl(n):
    if n>0:
        return 1
    elif n==0:
        return 0
    else:
        return -1
s1=0
s2=0
c1=0
c2=0
b=1
for i in range(n):
    if b==-1:
        if pl(s1+a1[i])!=-1:
            t=s1+a1[i]+1
            a1[i]-=t
            c1+=t
        s1+=a1[i]
        b=1
    else:
        if pl(s1+a1[i])!=1:
            t=-s1-a1[i]+1
            a1[i]+=t
            c1+=t
        s1+=a1[i]
        b=-1

b=-1
for i in range(n):
    if b==-1:
        if pl(s2+a2[i])!=-1:
            t=s2+a2[i]+1
            a2[i]-=t
            c2+=t
        s2+=a2[i]
        b=1
    else:
        if pl(s2+a2[i])!=1:
            t=-s2-a2[i]+1
            a2[i]+=t
            c2+=t
        s2+=a2[i]
        b=-1
print(min(c1,c2))

Measured memory_bytes: 15164
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define ii pair<int,int>
#define mp make_pair
using namespace std;
int dp[200005];
int  a[200005];
int main()
{
int n;
cin>>n;
dp[0] = 0;
int maxx = 0;
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);

    if(i > 1 && a[i] <= a[i-1])
    {
        dp[i]=dp[i-1]+1;
    }
    else
    {
        dp[i] = 0;
    }
    maxx = max(maxx , dp[i]);
}
cout<<maxx;

}


Measured memory_bytes: 1024
class ModComb
  def initialize(max, mod)
    @mod = mod
    @fac = Array.new(max + 1)
    @finv = Array.new(max + 1)
    @inv = Array.new(max + 1)
    @fac[0] = @fac[1] = 1
    @finv[0] = @finv[1] = 1
    @inv[1] = 1
    (2..max).each do |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
    end
  end

  def comb(n, k)
    return 0 if n < k
    return 0 if n < 0 || k < 0
    @fac[n] * (@finv[k] * @finv[n - k] % @mod) % @mod
  end
end

N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

MOD = 10 ** 9 + 7
sorted = A.sort
comb = ModComb.new(N, MOD)
ans = 0
N.times do |i|
  a = sorted[i]
  max_count = comb.comb(i, K - 1)
  min_count = comb.comb(N - i - 1, K - 1)
  ans = (ans + (a * max_count % MOD) - (a * min_count % MOD)) % MOD
end
puts ans

Measured memory_bytes: 11772
n,k = map(int,input().split())
MOD = 10**9 + 7

ans = 0
for i in range(k,n+2):
  mn = (i-1)*i//2
  mx = (2*n-(i-1))*i//2
  ans += mx-mn+1
  ans %= MOD
print(ans)

Measured memory_bytes: 63660
/*{{{*/
#include <bits/stdc++.h>
#ifdef DBG
int c_;
#define cout (c_?cerr:cout)
#define dbg(...) {if(!c_)cerr<<"\033[96;1m";++c_;\
__VA_ARGS__;--c_;if(!c_)cerr<<"\033[0m";}
#else
#define dbg(...)
#endif
#define st first
#define nd second
#define dprt(...) dbg(prt(__VA_ARGS__))
#define dmp(...) dprt(#__VA_ARGS__, __VA_ARGS__)
#define drprt(...) dbg(rprt(__VA_ARGS__))
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
#define rdmp(...) dbg(cerr<<#__VA_ARGS__<<": ";rprt(__VA_ARGS__))
using namespace std; using ll = long long;
template< typename t > using V = vector< t >;
template< typename t > void prt(const t& a){cout<<a<<'\n';}
template< typename t, typename... v > void prt(const t& a, v&&... b)
{cout<<a<<' ';prt(b...);}
template< typename t > void rprt(t a, const t& b){while(a!=b)cout<<(*a++)<<' ';cout << '\n';}
/*}}}*/

int n, x;
V< int > tb;

inline ll spr(int v)
{
    ++v;

    V< ll > ilo(tb.size() * 2);

    for (int i = 0; i < ilo.size(); ++i)
        ilo[i] = tb[(i >= tb.size()? i - tb.size() : i)];

    rdmp(all(ilo));

    deque< pair< int, int > > dq;

    for (int i = 0; i < ilo.size(); ++i)
    {
        while (dq.size() and dq.front().nd < i - v + 1)
            dq.pop_front();

        while (dq.size() and dq.back().st >= ilo[i])
            dq.pop_back();

        dq.push_back({ilo[i], i});

        ilo[i] = dq.front().st;
    }

    ll res = 0;
    for (int i = v - 1; i < v - 1 + n; ++i)
        res += ilo[i];

    rdmp(all(ilo));
    dmp(res);

    return res;
}

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

    cin >> n >> x;

    tb.resize(n);
    for (int& i : tb)
        cin >> i;

    ll res = LLONG_MAX;
    for (int i = 0; i < n; ++i)
        res = min(res, (ll)i * x + spr(i));

    prt(res);
}

Measured memory_bytes: 256
N, Q = map(int, input().split())

graph = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

val = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    val[p] += x

# 頂点1から順番に処理
stack = [1]

parent = [0] * (N+1)

# 頂点xと繋がっている頂点yをそれぞれ調べ、yがxの親である場合は何もしない。
# yがxの親でない場合は、yがxの子であるため、yの親としてxを登録し、次の処理対象としてstackし、yのカウンターにxの値を足す
while stack:
    # stackから頂点を1つ取り出す
    x = stack.pop()
    # stackから取り出した頂点とつながっている頂点それぞれについて処理
    for y in graph[x]:
        # yがxの親（xがyの子）
        if y == parent[x]:
            # 何もしない
            pass
        #xがyの親（yがxの子）
        else:
            # 頂点x, y繋がっているためどちらかが必ず親なので、xをyの親として登録
            parent[y] = x
            # yをxの子としてstack
            stack.append(y)
            # yのカウンターにxの値を足す
            val[y] += val[x]

print(' '.join(map(str,val[1:])))

Measured memory_bytes: 66948
#include <stdio.h>
#include <math.h>

int main(void)
{
	double r;
	double a,b;

	scanf("%lf",&r);

	a = r*r*3.141592653589;
	b = 2*r*3.141592653589;

	printf("%f %f\n",a,b);

	return 0;
}

Measured memory_bytes: 648
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll nCm(ll n, ll m){
    if(m == 0 || m == n){
        return 1;
    } else if(m == 1){
        return n;
    }
    return (nCm(n - 1, m) + nCm(n - 1, m - 1));
}

//-----------------------ここから-----------

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

    vector<int> mod4(n);
    int counter4 = 0;
    int counter2 = 0;
    for(int i = 0; i < n; i++){
        mod4[i] = a[i] % 4;
        if(mod4[i] == 0){
            counter4++;
        } else if(mod4[i] == 2){
            counter2++;
        }
    }
    if(counter4 + counter2 / 2 < n / 2){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <random>

using ll = long long;

//vector
template <class T>
using vec = std::vector<T>;

//namespace std
//{
//    template<>
//    class hash<Key>
//    {
//    public:
//        size_t operator() (const Key& key) const
//        {
//            size_t seed = 0;
//            auto i_hash = hash<int>()(key.i_th);
//            auto w_hash = hash<int>()(key.W);
//
//            seed ^= i_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
//            seed ^= w_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
//
//            return seed;
//        }
//    };
//}


void solve()
{
    using namespace std;
    int a, b;
    cin >> a >> b;

    int sum {};

    for (int i = 0; i < b - a; ++i)
    {
        sum += i;
    }

    cout << sum - a << endl;
}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int n,m,k;cin>>n>>m>>k;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= m; j++) {
			if (i * m + j * n - 2 * i * j == k){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    vector<int> cnt(N);

    ll ans = 1;
    for (int i = 0; i < N/2; i++){
        ans *= 2;
        ans %= MOD;
    }

    for (int i = 0; i < N; i++){
        cin >> a[i];
        cnt[a[i]]++;
    }

    if (N % 2 == 0){
        if (cnt[0] != 0) {
            ans = 0;
        }
        for (int i = 1; i < N; i += 2){
            if (cnt[i] != 2){
                ans = 0;
            }
        }
    } else {
        if (cnt[0] != 1) {
            ans = 0;
        }
        for (int i = 2; i < N; i += 2) {
            if (cnt[i] != 2) {
                ans = 0;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main(){
    int a,b; cin >> a >> b;

    for(int i=1;i<1500;i++){
        if((int)(i*.08) == a && (int)(i*.10) == b){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const ll MOD = 1000000007;

int main() {
    int n; cin >> n;
    vector<vector<int>> G(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < n; i++) {
        int u, k; cin >> u >> k;
        for (int j = 0; j < k; j++) {
            int v; cin >> v;
            G[u][v] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", G[i][j]);
            if (j < n) printf(" ");
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 3268
import java.util.Scanner;

class Main{
	static final long MOD = 1000000007;

	static int H, W, K;
	static long[][] dp = new long[110][10];
	static int ans = 0;
	static long n = 0;


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		n = sc.nextLong();

		if(n == 25){
			System.out.println("Christmas");
		}else if(n == 24){
			System.out.println("Christmas Eve");

		}else if(n == 23){
			System.out.println("Christmas Eve Eve");

		}else{
			System.out.println("Christmas Eve Eve Eve");

		}
	}

}







class Pair implements Comparable{
	int from;		//p
	int end;		//y
	int num;
	int bango;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <ctype.h>
#include <iomanip>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
// #include <pair> 
       
using namespace std;
       
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
 
// #define MAX 100010
 
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES
 
// long long binpow(long long a,long long b)
// {
//     if (b == 1) return a;
//     long long res = binpow(a, b/2)%MOD;
//     if (b % 2) return (res*((res*a)%MOD))%MOD;
//     else return (res * res)%MOD;
// }
 
// long long int fact(long long int a)
// {
//     if(a==0||a==1)
//         return 1;
//     long long int ans = 1;
//     for(int i=a;i>=1;i--)
//         ans = (ans * i);
//     return ans;
// }
 
// long long int ivmod(long long int a)
// {
//     return binpow(a,MOD-2);
// }
 
// long long int ncr(long long int a,long long int b)
// {
//     long long int pans=1;
//     for(int i =a;i>max(b,a-b);i--)
//         pans=pans*i;
//     long long int div = fact(min(b,a-b));
//     // cout<<ans<<"            "<<div<<endl;
//     pans = pans/div;
//     return pans;
// }

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif   
    string a;
    cin>>a;
    if(a[0]==a[2])
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<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 sz(x) int(x.size())
using ll=long long;
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N;
    cin>>N;
    vector<ll> A(N);
    rep(i,N){cin>>A.at(i);}
    if(N%2==0){
        ll ans;
        vector<ll> L(N/2+1),R(N/2+1);
        rep(i,N/2){
            L.at(i+1)=L.at(i)+A.at(2*i);
            R.at(i+1)=R.at(i)+A.at(N-1-2*i);
        }
        rep(i,N/2+1){
            ll now=L.at(i)+R.at(N/2-i);
            if(i==0){ans=now;}
            ans=max(ans,now);
        }
        cout<<ans<<endl;
        return 0;
    }

    //N奇数
    ll ans=0;
    rep(i,(N+1)/2){ans+=A.at(2*i);}
    vector<ll> ad((N-1)/2),adwa((N+1)/2);
    rep(i,(N-1)/2){
        ad.at(i)=A.at(2*i+1)-A.at(2*i+2);
    }
    rep(i,(N-1)/2){
        adwa.at(i+1)=adwa.at(i)+ad.at(i);
    }
    set<pair<ll,ll>> s;
    rep(i,(N+1)/2){
        s.insert({adwa.at(i),i});
    }

    ll kotae;
    rep(i,(N+1)/2){
        ll ansn=ans-A.at(2*i);
//cout<<ansn<<endl;
        pair<ll,ll> p;
        p=*rbegin(s);
        ll now=p.first-adwa.at(i);
        ansn+=now;

//cout<<ansn<<endl;
        if(i==0){kotae=ansn;}
        kotae=max(kotae,ansn);
        s.erase({adwa.at(i),i});
    }
    cout<<kotae<<endl;
    //cout<<ans<<endl;

    return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int ans;
  if(n>=400 && n<=599) ans = 8;
  else if(n>=600 && n<=799) ans = 7;
  else if(n>=800 && n<=999) ans = 6;
  else if(n>=1000 && n<=1199) ans = 5;
  else if(n>=1200 && n<=1399) ans = 4;
  else if(n>=1400 && n<=1599) ans = 3;
  else if(n>=1600 && n<=1799) ans = 2;
  else ans = 1;
  cout << ans << '\n';
  return 0;
}


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

int d[5][16] = {0};

int main(){
    int n;
    
    
    scanf("%d", &n);
    int i;
    for(i = 0; i < n; i++){
        char c, c1;
        int a;
        scanf(" %c %d", &c, &a);
        // printf("%c %d\n", c, a);
        if(c == 'S') d[0][a - 1] = 1;
        else if(c == 'H') d[1][a - 1] = 1;
        else if(c == 'C') d[2][a - 1] = 1;
        else d[3][a - 1] = 1;
    }
    int j;
    char m;
    for(i = 0; i < 4; i++){
        for(j = 0; j < 13; j++){
            if(d[i][j] == 0){
                if(i == 0){
                    m = 'S';
                }else if(i == 1){
                    m = 'H';
                }else if(i == 2){
                    m = 'C';
                }else{
                    m = 'D';
                }
                printf("%c %d\n", m, j + 1);          
            }
        }
    }
    return 0;
}

Measured memory_bytes: 596
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ans = 0
    for i in range(N):
        right = i + 2
        for left in range(i+1, N):
            while right < N and L[right] < L[i] + L[left]:
                right += 1
            ans += right - (left+1)
            if left == right:right += 1
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 42476
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ans = [0 for _ in range(N)]
n = 1
while True:
    for i in range(M):
        for j in range(2):
            if n == ab[i][j]:
                ans[n-1] += 1
    if n == N:
        break
    n += 1
for i in range(N):
    print(ans[i])

Measured memory_bytes: 9052
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxh=15;
const int maxw=1005;
const int INF=0x3f3f3f3f;
int h,w,k,ans;
bool a[maxh][maxw];
int div_[maxh][maxw];
int get_div(int ways)
{
    memset(div_,0,sizeof(div_));
    int real[maxh]={},cnt=0;
    for(int i=0;i<(h-1);i++)
        if(ways&(1<<i))
            real[++cnt]=i+1;
    real[++cnt]=h;
    for(int i=1;i<=cnt;i++)
        for(int col=1;col<=w;col++)
            for(int row=real[i-1]+1;row<=real[i];row++)
                div_[i][col]+=a[row][col];
    return cnt;
}
bool check()
{
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if(div_[i][j]>k)
                return false;
    return true;
}
void solve()
{
    int num[maxh]={};
    for(int i=0;i<(1<<(h-1));i++)
    {
        memset(num,0,sizeof(num));
        int blocks=get_div(i),res=blocks-1;
        if(!check()) continue;
        for(int col=1;col<=w;col++)
        {
            for(int row=1;row<=blocks;row++)
                num[row]+=div_[row][col];
            bool sign=true;
            for(int row=1;row<=blocks;row++)
                if(num[row]>k)
                {
                    sign=false;
                    break;
                }
            if(!sign)
            {
                res++;
                for(int row=1;row<=blocks;row++)
                    num[row]=div_[row][col];
            }
        }
        ans=min(ans,res);
    }
}
int main()
{
    scanf("%d%d%d",&h,&w,&k);
    string ss;
    for(int i=1;i<=h;i++)
    {
        cin>>ss;
        for(int j=1;j<=w;j++)
            a[i][j]=(ss[j-1]-'0');
    }
    ans=INF;
    solve();
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
  int A,B,C,cnt,X; cin>>A>>B>>C>>X;
  for(int i=0;i<A+1;i++)for(int j=0;j<B+1;j++)for(int k=0;k<C+1;k++)cnt+=500*i+100*j+50*k==X;
  cout<<cnt<<endl;
  return 0;
}


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

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

using namespace std;
const long long INF = 1LL << 61;

int main() {
	int A, B, C; cin >> A >> B >> C;
	cout << max(C - (A - B), 0);
}

Measured memory_bytes: 256
/************
* 	@Just Another Source code by: ankit.sangwan1999
*	@created on: 24 Jun 2020
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) //;cout.tie(NULL)
#define ll long long
const int mod = 1e9+7;
const long double pie = 3.14159265358979323846;
#define endl '\n'
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, ll> ma; // orderd_map using pb_ds
int dp[101][100005];
int arr[101];
int fun(int ind, int sum, int n){
	if(sum<0) return 0;
	if(ind>=n){
		if(sum==0) return 1;
		else return 0;
	}
	if(dp[ind][sum] != -1) return dp[ind][sum];
	int ans = 0;
	for(int i=0;i<=arr[ind];i++){
		if(i>sum) break;
		ans = (ans%mod + fun(ind+1, sum-i, n)%mod)%mod;
	}

	return dp[ind][sum] = ans;
}

void solve(){
	// memset(dp, -1, sizeof(dp));
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}

	// cout<<fun(0, k, n);



	// BOTTOM-UP;
	memset(dp, 0, sizeof(dp));
	int pre[100000+1];
	memset(pre, 0, sizeof(pre));
	pre[0] = 1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=k;j++){
			if(i==0 and j!=0){
				dp[i][j] = 0;
			}
			else if(j==0){
				dp[i][j] = 1;
			}
			else{
				if(arr[i-1]<j){
					// take prefix sum from 0th till jth index.
					dp[i][j] = (pre[j]%mod - pre[j-arr[i-1]-1]%mod + mod)%mod;
				}
				else{
					// take prefix sum till jth index for lenght arr[i-1]
					dp[i][j] = pre[j]%mod;
				}
			}
		}
		// updating the pre sum array for next row.
		pre[0] = 1;
		for(int j=1;j<=k;j++){
			pre[j] = (pre[j-1]%mod + dp[i][j]%mod)%mod;
		}
	}

	// for(int i=0;i<=n;i++){
	// 	for(int j=0;j<=k;j++){
	// 		cout<<dp[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }

	cout<<dp[n][k];


}
signed main(){

    fastio;
    int t=1;
    //cin>>t;

    while(--t>=0){
    	solve();
    }
		

    return 0;
}

Measured memory_bytes: 43460
h,w=map(int,input().split())
s=[]
for i in range(h):
  s.append([i for i in input()])
l=[["" for i in range(w)] for j in range(h)]
for hh in range(h):
  for ww in range(w):
    if s[hh][ww]=="#":
      l[hh][ww]="#"
    else:  
      cnt=0
      for hhh in [-1,0,1]:
        for www in [-1,0,1]:
          if 0<=hh+hhh<h and 0<=ww+www<w and s[hh+hhh][ww+www]=="#":
            cnt+=1
      l[hh][ww]=cnt
for i in l:
  for j in i:
    print(j,end="")
  print()  

Measured memory_bytes: 3444
#include<stdio.h>

int main(){
	int a, b;

	a = 1;
	b = 1;

	int j;

	for (j = 0; j < 9; j++){

		int i;
		for (i = 0; i < 9; i++){
			printf("%d", a);
			printf("x");
			printf("%d", b);
			printf("=");
			printf("%d\n", a * b);
			b = b + 1;
		}
		b = 1;
		a = a + 1;
	}
	return 0;
}

Measured memory_bytes: 524