akhauriyash/Code-Regression huggingface dataset:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    N, M = map(int, input().split())
    X = sorted(map(int, input().split()))
    h = [j - i for i, j in zip(X, X[1:])]
    heapify(h)
    print(sum(heappop(h) for _ in range(M - N)))

main()


Measured memory_bytes: 90148
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


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

    if(c-a-b >= 0) {
        if(4*a*b < (c-a-b)*(c-a-b)) cout << "Yes" << endl;
        else cout << "No" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

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

using namespace std;

int main(){
  long long int x,y;
  cin>>x>>y;
  long long int ans;
  if(x>=3 && y>=3){
    ans=(x-2)*(y-2);
  }
  else if(x==2 || y==2){
    ans=0;
  }
  else{
    ans=x*y-2;
    if(ans<0)ans=1;
  }
  cout<<ans<<endl;
}

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

int main(){
    int N,K,X,Y;
    cin >> N;
    cin >> K;
    cin >> X;
    cin >> Y;

    int sum = 0;

    if (N > K){
        sum = X * K + Y * (N - K);
        cout << sum;
    }
    
    if (N <= K){
        sum = X * N;
        cout << sum;
    }

    return 0;
}

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

int main(void){
 int X;
 int Y;
 int ans;
cin >> X >> Y;
map<int,int> score;
  
score[1]=300000;
score[2]=200000;
score[3]=100000;

ans =0;
  
if(X==1 and Y==1) ans+=400000;
try{
ans+=score[X];
}catch(exception e){
}
try{
ans+=score[Y];
}catch(exception e){
}

cout << ans;
}

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

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

  int count;
  if (a == b && b == c && c == a) count = 1;
  else if (a == b || b == c || c == a) count = 2;
  else count = 3;
  cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>
  
int main() {
  int N, ans = 0, last = 0; std::cin >> N;
  for(int i = 0; i < N; ++i) {
    int A; std::cin >> A;
    if(A != last+1) ++ans;
    else ++last;
  }
  if(ans == N) ans = -1;
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main()
{
	
	const int MAX = 100000;
	
	int n;
	long long int k;
	cin >> n >> k;
	
	long long int buckets[MAX];
	int a,b;
	
	for(int i=0; i<MAX; i++){
		buckets[i] = 0;
	}										// 初期化
	
	for (int i=0; i<n; i++){
		cin >> a >> b;
		buckets[a-1] += b;
	}
	
	long long int count = 0;
	
	for (int i=0; i<MAX; i++){
		count += buckets[i];
		if (count >= k){
			cout << i+1 << "\n";
			break;
		}
	}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long LL;
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second

using namespace std;

int main(){
	DRI(n);
	char s[100004];
	RS(s);
	int lastsame=-1;
	//VI lasts(26,-1);
	VI cs(26,1);
	LL res=1;
	REP(i,n){
		/*lastsame=max(lastsame,lasts[s[i]]);
		res+=i-lastsame;
		lasts[s[i]]=i;*/
		cs[s[i]-'a']++;
	}
	int mod=1000000007;
	REP(i,26){
		res*=cs[i];
		res%=mod;
	}
	res+=mod-1;
	res%=mod;
	int rr=res;
	printf("%d\n",rr);
}


Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, v[N], a, b;
bool check(int m) {
	long long need = 0;
	for (int h, i = 0; i < n; ++i) {
		h = max(0ll, v[i] - (ll)b*m);
		int x = a - b;
		need += (h + x - 1) / x;
	}
	return need <= m;
}
int main()
{
	scanf("%d", &n);
	scanf("%d%d", &a, &b);
	for (int i = 0; i < n; ++i)
		scanf("%d", &v[i]);
	sort(v, v + n);
	reverse(v, v + n);
	int l = 1, r = 1e9, m, res = 1e9 + 1;
	while (l <= r) {
		m = (l + r) / 2;
		if (check(m)) {
			r = m - 1;
			res = m;
		}
		else
			l = m + 1;
	}
	printf("%d\n", res);
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
clock_t startTime;
long double getTime(){
	return (long double)(clock()-startTime)/CLOCKS_PER_SEC;
}

int main(){
	startTime=clock();
	int n;
	cin >> n;
	ll a[n],b[n];
	ll k=0;
	ll sum=0;
	FOR(i,n){
		cin >> a[i];
	}
	FOR(i,n){
		cin >> b[i];
	}
	FOR(i,n){
		sum+=b[i]-a[i];

		if(a[i] < b[i])
		k+=(b[i]-a[i]+1)/2;
	}
	
	if(sum < 0) {cout << "No"; return 0;}
	else if(k > sum) cout << "No";
	else cout << "Yes"; 


	return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include <vector>

int main()
{
    int N;
    std::cin >> N;

    int other = 0;
    std::vector<int> rate_cnt(8);
    for (int i = 0; i < N; i++) {
        int a;
        std::cin >> a;

        if (a < 3200)
            rate_cnt[a / 400] += 1;
        else
            other += 1;
    }

    int kind_of_color = 0;
    for (int i = 0; i < 8; i++) {
        kind_of_color += (rate_cnt[i] > 0);
    }

    int min = kind_of_color == 0 ? 1 : kind_of_color;
    int max = kind_of_color + other;

    std::cout << min << " " << max << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    string s;
    cin>>s;
    int ans=0;
    rep(i,s.size()){
        if(s[i]=='2')ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N,M,X = list(map(int, input().rstrip().split()))

C_list = []
A_list = []

for i in range(N):
    inp = list(map(int, input().rstrip().split()))
    C_list.append(inp[0])
    A_list.append(inp[1:])
#-----

bit = 1 << N
max_price = sum(C_list)*2
min_price = max_price

for b in range(bit):
    price = 0
    study = [0]*M
    
    for i in range(N):
        if (b & (1 << i)):
            price += C_list[i]
            
            for j in range(len(A_list[i])):
                study[j] += A_list[i][j]
    
    if min(study) >= X:
        min_price = min(min_price, price)


print(min_price if min_price != max_price else -1)


Measured memory_bytes: 9236
k = int(input())

ans = 1
cnt = 0
while cnt < k:
    # print(ans, cnt)
    if ans <= 9:
        cnt+=1
        ans+=1
        continue
    li = list(map(int, list(str(ans))))
    flag=1
    for i in range(len(li)-1):
        if abs(li[i]-li[i+1]) > 1:
            ans+=10**(len(li)-i-2)
            flag=0
            break
    if flag:
        cnt+=1
        ans+=1
print(ans-1)

Measured memory_bytes: 43200
package main

import (
  "fmt"
  "math"
)

func main() {
  var n, k int
  fmt.Scan(&n)
  fmt.Scan(&k)
  if int(math.Ceil(float64(n) / 2)) >= k {
    fmt.Println("YES")
  } else {
    fmt.Println("NO")
  }
}


Measured memory_bytes: 512
import scala.annotation.tailrec
import scala.collection.mutable
object Main extends App {
  import scala.io.StdIn._

  val n = readInt()
  val blocks = Array.fill(n){
    readLine.trim.split(' ').map(_.toInt) match {
      case Array(w, h) ⇒ Block(w, h)
      case _ ⇒ ???
    }
  }
  val (nodes, source, sink) = makeNode(blocks)
  println(n - maxFlow(nodes, source, sink))
  def makeNode(blocks: Array[Block]): (Array[List[Flow]], Int, Int) = {
    val source = blocks.length * 2
    val sink = source + 1
    val nodes = Array.fill(sink + 1) {Nil: List[Flow]}
    for (i ← blocks.indices; j ← blocks.indices; if i != j) {
      if (blocks(i).canPutOn(blocks(j))) {
        addEdge(nodes, i * 2, j * 2 + 1)
      }
    }
    for (i ← blocks.indices) {
      addEdge(nodes, source, i * 2)
      addEdge(nodes, i * 2 + 1, sink)
    }
    (nodes, source, sink)
  }
  def maxFlow(nodes: Array[List[Flow]], source: Int, sink: Int): Int = {
    val depth = Array.fill(nodes.length){0}
    val queue = mutable.Queue[Int]()
    def setDepth(): Unit = {
      depth.indices.foreach(i ⇒ depth(i) = -1)
      depth(source) = 0
      queue.enqueue(source)
      while (queue.nonEmpty) {
        val current = queue.dequeue()
        for (Flow(to, hasFlow) ← nodes(current) if hasFlow && depth(to) == -1) {
          depth(to) = depth(current) + 1
          queue.enqueue(to)
        }
      }
    }
    val searching = nodes.clone()
    def dfs(current: Int): Boolean = {
      if (current == sink) return true
      else {
        while (true) {
          searching(current) match {
            case Nil ⇒ return false
            case (f@Flow(to, true))::rest if depth(current) < depth(to) && dfs(to) ⇒
              f.hasFlow = false
              f.pair.hasFlow = true
              return true
            case _::rest ⇒ searching(current) = rest
          }
        }
        false
      }
    }
    var count = 0
    var hasFlow = true
    while(hasFlow) {
      hasFlow = false
      setDepth()
      searching.indices.foreach(i ⇒ searching(i) = nodes(i))
      while(dfs(source)) {
        hasFlow = true
        count += 1
      }
    }
    count
  }
  class Block private (val height: Int, val width: Int) {
    def canPutOn(that: Block): Boolean = height < that.height && width < that.width
  }
  object Block {
    def apply(height: Int, width: Int) : Block = new Block(math.min(height, width), math.max(height, width))
  }
  def addEdge(nodes: Array[List[Flow]], from: Int, to: Int): Unit = {
    nodes(from) ::= Flow(to, hasFlow = true)
    nodes(to) ::= Flow(from, hasFlow = false)
    nodes(from).head.pair = nodes(to).head
    nodes(to).head.pair = nodes(from).head
  }
  case class Flow(to: Int, var hasFlow: Boolean) {
    private var mPair: Option[Flow] = None
    def pair: Flow = mPair.get
    def pair_=(that: Flow): Unit = mPair = Some(that)
  }
}


Measured memory_bytes: 49476
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353,INF=1e18;

int N,M,Q;
vector<vector<int>> ans;
void dfs(vector<int> po,int n){
    if(n==N-1){ans.pb(po);return;}
    int f=po.at(n);
    for(int i=f;i<=M;i++){
        po.at(n+1)=i;
        dfs(po,n+1);
    }
    return;
}

int main() {
    
    cin>>N>>M>>Q;
    ans.resize(0,vector<int>(N));
    vector<int> a(Q),b(Q),c(Q),d(Q);
    rep(i,Q)cin>>a.at(i)>>b.at(i)>>c.at(i)>>d.at(i);

    vector<int> start(N);
    start.at(0)=1;
    dfs(start,0);

//rep(i,sz(ans)){cout<<ans.at(i).at(N-1)<<" ";}

    ll point=0;
    rep(i,sz(ans)){
        ll score=0;
        rep(j,Q){if(ans.at(i).at(b.at(j)-1)-ans.at(i).at(a.at(j)-1)==c.at(j)){score+=d.at(j);}}
        chmax(point,score);
    }
    cout<<point<<endl;
}


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

const int maxn = 105;
string s[maxn];
int dp[maxn][maxn];

int main(int argc, char const *argv[])
{
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    cin >> s[i];
  }
  memset(dp, 63, sizeof dp);
  dp[0][0] = 0;
  if(s[0][0] == '#'){
    dp[0][0] = 1;
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(s[i][j] == '.'){
        if(i + 1 < n){
          if(s[i + 1][j] == '.'){
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
          }else {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
          }
        }
        if(j + 1 < m){
          if(s[i][j + 1] == '.'){
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
          }else {
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
          }
        }
      }else {
        if(i + 1 < n){
          dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }if(j + 1 < m) {
          dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
        }
      }
    }
  }
  cout << dp[n - 1][m - 1] << endl;

  return 0;
}

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

using namespace std;

int main(){
	int h,w;
	cin >> h >> w;
	vector<vector<bool> > sky(h, vector<bool>(w,false));
	for(int i= 0; i < h; i++) for(int j = 0; j < w; j++){
		char c; cin >> c;
		if(c == 'c'){ sky[i][j] = true;}
	}
	vector<vector<int> > time(h, vector<int>(w,-1));
	for(int i = 0; i < h; i++){
		int tmp = -1;
		for(int j = 0; j < w; j++){
			if(sky[i][j]){
				tmp = 0;
			}
			time[i][j] = tmp;
			if(tmp != -1){ tmp++;}
		}
	}

	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cout << time[i][j];
			if(j != w-1){ cout << " "; }
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REYNA(i, a, b) for (int i=(a); i<(b); ++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PII, PII> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int mod = 1e9+7;
const int inf = 1e9+9;
const int maxn = 110;

bool plan[maxn][maxn];
int a, b;

int main()
{
	boost;
	cin >> a >> b;
	FOR(i, 1, 100)
		FOR(j, 1, 100)
			if (j <= 50) plan[i][j] = 0;
			else plan[i][j] = 1;
	
	a--; b--;
	FOR(i, 1, 100)	
		FOR(j, 1, 40)
			if (b > 0 && i % 2 == 0 && j % 2 == 0) plan[i][j] = 1, --b;
	
	FOR(i, 1, 100)
		FOR(j, 53, 100)
			if (a > 0 && i % 2 == 0 && j % 2 == 0) plan[i][j] = 0, --a;
	
	cout << "100 100\n";
	FOR(i, 1, 100)
		FOR(j, 1, 100) {
			if (!plan[i][j]) cout << ".";
			else cout << "#";
			if (j == 100) cout << "\n";
		}
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
int main() {
	int A, B, C;
	cin >> A >> B >> C;
	if(B / A <= C)
		cout << B / A;
	else
		cout << C; 
	return 0;
} 

Measured memory_bytes: 256
N,Y = map(int,input().split())
f=False
for i in range(N+1):
    for j in range(N+1):
        k = N-i-j
        if k < 0:
            continue
        if 10000*i + 5000*j + 1000*k == Y:
            print(i,j,k)
            f=True
            break
    if f :
        break
if (not f): 
    print(-1,-1,-1)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<string.h>
#include<cmath>
#include<iomanip>
using namespace std;
#define ll long long
#define pb push_back
#define INF (int)10000
#define f first
#define s second

double distance(int x1,int y1,int x2,int y2){
	double ans =0;
	int me1 = abs(x1-x2);
	int me2 = abs(y1-y2);
	ans = me1*me1+me2*me2;
	ans = sqrt(ans);
	return ans;
}
int main()
{
    //fast;
    int fac[9];
    fac[0] =1;
    for(int i=1;i<9;i++){
    	fac[i] = fac[i-1]*i;
	}
	int n;
	vector<pair<int,int>> v(9);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>v[i].f>>v[i].s;
	}
	double ans = 0;
	int a[8] = {0,1,2,3,4,5,6,7};
	//int a[n];
	//for(innt i =0;i<n)
	do{
		for(int i=0;i<n-1;i++){
			ans += distance(v[a[i]].f,v[a[i]].s,v[a[i+1]].f,v[a[i+1]].s);
		}
	}while(next_permutation(a,a+n));
	ans = ans/fac[n];
	cout<<fixed<<setprecision(10)<<ans;
}

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

int main(){
   int n,m;
   cin >> n >> m;
   vector<set<int>> road(n);
   set<int> res;
   vector<int> h(n);
   for (int i=0;i<n;++i){
       cin >> h[i];
   }

   for (int i=0;i<m;i++){
       int a,b;
       cin >> a >> b;
       road[a-1].insert(b);
       road[b-1].insert(a);
   }

   for (int i=0;i<n;++i){
       //cout << i << "{";
       if(road[i].size()==0){
           res.insert(i+1);
       }else{
           bool flag=true;
           for(int x : road[i]) {
               //cout << x << ",";
               if(h[i]<=h[x-1]){
                   flag=false;
                   break;
               }
            }
            if(flag){
                res.insert(i+1);
            }
       }
       //cout << "}" << endl;

   }
   /*
   for (int x : res){
       cout << x << ":";
   }
   cout << endl;
   */

   cout << res.size() << endl;
}

Measured memory_bytes: 19628
#include <stdio.h>
#include <string.h>
int main(void)
{
    int i,j,k,m,x;
    char n[200],n1[200];
    while(1){
        scanf("%s",n);
        if(n[0]=='-')break;
        x=strlen(n);//文字数を数える
        scanf("%d",&k);//回数を入力
        for(m=0;m<k;m++){
            scanf("%d",&i);
            strncpy(n1,n,i);
            n1[i] = '\0';//n1の作成完了
            for(j=0;j<x-i;j++)n[j]=n[i+j];
            n[j] = '\0';//nの作成完了
            strcat(n,n1);//n+n1をする
        }
        printf("%s\n",n);
    }
    return 0;
}

Measured memory_bytes: 604
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int com(const char *x,const char *y){
    return strcmp(x,y);
}

int main(){
    int s=0,i,count=0;
    char w[101]={};
    scanf("%s",w);
    while (w[s]!='\0') s++;
    qsort(w,s , sizeof(w[0]), com);
    if (s==1) {
        printf("No");
        return 0;
    }
    for (i=0; i<s-1; i++) {
        count++;
        if (w[i]!=w[i+1]) {
            if (count%2!=0) {
                printf("No");
                return 0;
            }
            count=0;
        }
    }
    printf("Yes");
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Grand032B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var isEven = N % 2 == 0;
            var pairNum = isEven ? 1 + N : N;
            var a = new int[10000];
            var b = new int[10000];
            var index = 0;
            for(int i = 0;i<N-1;i++)
            {
                for(int j = i+1;j<N;j++)
                {
                    if(i+j+2 != pairNum)
                    {
                        a[index] = i + 1;
                        b[index] = j + 1;
                        index++;
                    }
                }
            }
            Console.WriteLine(index);
            for(int i=0;i<index;i++)
            {
                Console.WriteLine(a[i] + " " + b[i]);
            }
        }
    }
}


Measured memory_bytes: 13180
import sys

n, m = map(int, raw_input().split())

a = [0] * (n + 1)
for _ in xrange(m):
	x, y = map(int, raw_input().split())
	if x > y:
		x, y = y, x
	if x == 1:
		a[y] += 1
	if y == n:
		a[x] += 1
for i in xrange(2, n):
	if a[i] == 2:
		print "POSSIBLE"
		sys.exit(0)
print "IMPOSSIBLE"

Measured memory_bytes: 4228
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int S[N],n,u[N][N],l[2][N],r[2][N],flag[N][N];
char A[N][N];
int main(){
	scanf("%d",&n);
	for (register int i=1;i<=n;++i)scanf("%s",A[i]+1);
	for (register int i=1;i<=n;++i)
		for (register int j=1;j<=n;++j)flag[i][j]=A[i][j]>='0'&&A[i][j]<='9';
	for (register int i=0;i<=n;++i)
		for (register int j=0;j<=n;++j)u[i][j]=flag[i][j]?min(i,min(u[i-1][j],u[i][j-1])):1<<30;
	long long ans=0;
	for (register int x=1;x<=n;++x){
		for (register int i=x;i;--i){
			int t=i&1;
			for (register int j=1;j<=n;++j)S[j]=S[j-1]+(u[x][j]<=i?A[x][j]-'0':0);
			for (register int j=n+1;j;--j){
				if (flag[i][j]){
					if (i<x){
						l[t][j]=min(l[t][j+1],l[t^1][j]);
						r[t][j]=max(r[t][j+1],r[t^1][j]);
					}
					else l[t][j]=j,r[t][j]=max(j,r[t][j+1]);
					if (l[t][j]<=r[t][j])ans+=(A[i][j]-'0')*(S[r[t][j]]-S[l[t][j]-1]-(i==x?A[i][j]-'0':0));
				}
				else l[t][j]=1e9,r[t][j]=-1;
			}
		}
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 9216
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	s := getString()
	n := len(s)

	if n == 2 {
		if s[0] == s[1] {
			out(1, 2)
		} else {
			out(-1, -1)
		}
		return
	}

	for i := 0; i < n-2; i++ {
		if s[i] == s[i+1] || s[i] == s[i+2] || s[i+1] == s[i+2] {
			out(i+1, i+3)
			return
		}
	}
	out(-1, -1)
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <limits>
#include <string>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n); i > 0; i--)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
using lint = long long;
using P = pair<int, int>;
constexpr int MOD = 1e9 + 7;

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;
 
    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };
 
    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }
 
    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }
 
    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
 
    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }
 
    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

using mint = ModInt<MOD>;

int A, B, C, F, H, I, J, K, L, M, N, S, T, U, W;
// lint A, B, F, H, I, J, K, L, M, N, S, T, U, W;
// string A, B;
// int ans;

int itsq(int n) {
	if (n == 1) return 2;
	if (n % 2 == 0) {
		return itsq(n / 2) * itsq(n / 2) % MOD;
	} else {
		return 2 * itsq(n / 2) * itsq(n / 2) % MOD;
	}
}

int itex(int n, int e) {
	if (n == 1) return e % MOD;
	if (n % 2 == 0) {
		return itsq(n / 2) * itsq(n / 2) % MOD;
	} else {
		return e * itsq(n / 2) * itsq(n / 2) % MOD;
	}
}

int gen(int n) {
	if (n == 0 || n == 1) return 1;
	return n * gen(n - 1) % MOD;
}

mint comb(int n, int r) {
	mint rst = 1;
	rep1(i, r) {
		rst *= n - i + 1;
		rst /= i;
	}
	return rst;
}

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

	cin >> N >> A >> B;

	mint ans = mint(2).pow(N);
	mint a = comb(N, A);
	mint b = comb(N, B);

	cout << ans - a - b - 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  int a=100,b=1000,c=10000;
  cin >> a >> b >> c;
  int n[3] = {a, b, c};


  for(int i=0; i<3; i++){
    int tmp = n[i];
    [&]()->void{
      for(int j=i-1; j>=0; j--){
        if(tmp<n[j]){
          n[j+1] = n[j];
        } else {
          n[j+1] = tmp;
          return;
        }
      }
      n[0] = tmp;
    }();
  }
  cout << n[0] << " " << n[1] << " " << n[2] << "\n";
  return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;

int main(){
    string S;
    cin >> S;
    i64 sum;
    i64 ans=0;
    REP(bit,(1<<S.size()-1)){
        sum = S[0]-'0';
        REP(i,S.size()-1){
            if(bit & (1<<i)){
                ans += sum;
                sum = S[i+1]-'0';
            }else{
                sum = 10*sum + S[i+1]-'0';
            }
        }
        ans += sum;
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
void fin(int n){
  cout<<n<<endl;
  exit(0);
}
const int inf=1e7;
//main
signed main(){
  string s,t;cin>>s>>t;
  int S=s.size(),T=t.size();
  string K;while(K.size()<T)K+=s;K=t+"#"+K+s+s;
  //cout<<K<<endl;
  std::vector<int> A(inf,-1);
  int j=-1;
  for(int i=0;i<K.size();i++){
    while(j>=0&&K[i]!=K[j])j=A[j];
    j++;
    A[i+1]=j;
  }
  std::vector<int> match(inf,0);
  for(int i=0;i<S;i++)if(A[2*T+S+i]==T)match[i]++;
  std::vector<int> d(inf),edge[inf];
  for(int i=0;i<S;i++)if(match[i])edge[i].push_back((i+T)%S);
  std::vector<int> si(inf,0);
  for(int i=0;i<S;i++)for(int p:edge[i])si[p]++;
  queue<int> que;
  for(int i=0;i<S;i++)if(si[i]==0)que.push(i);
  int ans=0;
  while(que.size()){
    int p=que.front();que.pop();
    for(int q:edge[p]){
      d[q]=max(d[q],d[p]+1);ans=max(ans,d[q]);
      if(--si[q]==0)que.push(q);
    }
  }
  //for(int i=0;i<30;i++)cout<<A[i]<<" ";cout<<endl;
  //for(int i=0;i<S;i++)for(int p:edge[i])cout<<i<<" "<<p<<endl;
  for(int i=0;i<S;i++)if(si[i])fin(-1);
  fin(ans);
}


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

using namespace std;
using ll = long long;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long sx, long long sy, long long tx, long long ty){
  string s = "";
  for(ll i=0; i<tx-sx; i++)
    s.push_back('R');
  for(ll i=0; i<ty-sy; i++)
    s.push_back('U');
  for(ll i=0; i<tx-sx; i++)
    s.push_back('L');
  for(ll i=0; i<ty-sy; i++)
    s.push_back('D');
  s.push_back('D');
  for(ll i=0; i<tx-sx+1; i++)
    s.push_back('R');
  for(ll i=0; i<ty-sy+1; i++)
    s.push_back('U');
  s.push_back('L');
  s.push_back('U');
  for(ll i=0; i<tx-sx+1; i++)
    s.push_back('L');
  for(ll i=0; i<ty-sy+1; i++)
    s.push_back('D');
  s.push_back('R');
  std::cout << s << std::endl;
}

int main(){
  long long sx;
  scanf("%lld",&sx);
  long long sy;
  scanf("%lld",&sy);
  long long tx;
  scanf("%lld",&tx);
  long long ty;
  scanf("%lld",&ty);
  solve(sx, sy, tx, ty);
  return 0;
}


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

int main(){
	ll a,b;
	cin>>a>>b;
	if((a+b)%3==0 | a%3==0 | b%3==0){
		cout<<"Possible"<<endl;
	}else{
		cout<<"Impossible"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n = int(input())
edge = [[] for i in range(n+1)]
for i in range(n-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
dist = dijkstra_heap(0)
for i in dist:
    print(i%2)

Measured memory_bytes: 49132
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    ll n,w;
    cin>>n>>w;
    ll W[n],V[n];
    for(ll i=0;i<n;i++)cin>>W[i]>>V[i];
    ll dp[w+1]={0};
    for(ll i=0;i<n;i++)
    {
        for(ll j=w;j>=W[i];j--)
        {
            dp[j]=max(dp[j],V[i]+dp[j-W[i]]);
        }
        
    }
    
    ll maxi=dp[0];
    for(ll i=1;i<=w;i++)
    {
        maxi=max(maxi,dp[i]);
    }
    
    cout<<maxi<<endl;
    

}

Measured memory_bytes: 4372
D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if (1 << i) & cur: continue
        ip = i*100*p
        if ip > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            h = g(cur | (1 << i), n + p, left - ip - c)
            ret = min(ret, h)
    return ret

print(f(0, 0, G))

Measured memory_bytes: 44908
S = list(input())
ls = len(S)
n = ls - 1
ans = 0
from copy import deepcopy
for i in range(2 ** n):
    siki = deepcopy(S)
    add = 1
    for j in range(n):
        if ((i >> j) & 1):
            siki.insert(j+add, "+")
            add += 1
    # print("".join(siki))
    ans += eval("".join(siki))
print(ans)


Measured memory_bytes: 3444
'use strict'
function main(input) {
  input = input.trim().split('\n')
  let size = input.shift().split(' ').map(val => Number(val))
  let sizeDiff = size[0] - size[1]
  let N = []
  let M = []
  let result = 0

  for (let i = 0; i < size[0]; i++) {
    N.push(input.shift())
  }
  for (let i = 0; i < size[1]; i++) {
    M.push(input.shift())
  }

  for (let i = 0; i <= sizeDiff; i++) {
    while (result !== -1) {
      result = N[i].indexOf(M[0], result)
      if (result !== -1) {
        let check = true
        for (let j = 1; j < size[1]; j++) {
          if (check) {
            check = N[i+j].indexOf(M[j], result) === result
          }
        }
        if (check) {
          console.log('Yes')
          return
        }
      }
      if (result !== -1) result++
    }
    result = 0
  }
  console.log('No')
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
<?php

class Answer
{
    private $sequence_len;
    private $sequence;

    public function __construct()
    {
        while (1) {
            $line = FGETS(STDIN);
            if ($line == false) {
                break;
            }
            $line = trim($line);
            $lines[] = $line;
        }
        $this->sequence_len = $lines[0];
        $this->sequence = explode(' ', $lines[1]);
    }

    public function getAnswer()
    {
        $select = $this->selectionSort($this->sequence);
        $bubble = $this->bubbleSort($this->sequence);
        echo implode(' ', $bubble), PHP_EOL;
        echo 'Stable', PHP_EOL;
        if ($select === $bubble) {
            echo implode(' ', $select), PHP_EOL;
            echo 'Stable', PHP_EOL;
        } else {
            echo implode(' ', $select), PHP_EOL;
            echo 'Not stable', PHP_EOL;
        }
        
    }

    public function selectionSort($sequence)
    {
        $seq = $sequence;
        for ($i = 0; $i < $this->sequence_len; $i++) {
            $minj = $i;
            for ($j = $i; $j < $this->sequence_len; $j++) {
                if ($seq[$j][1] < $seq[$minj][1]) {
                    $minj = $j;
                }
            }
            if ($i != $minj) {
                list($seq[$i], $seq[$minj]) = array($seq[$minj], $seq[$i]);
            }
        }
        return $seq;
    }
        
    public function bubbleSort($sequence)
    {
        $seq = $sequence;

        for ($i = 0; $i < $this->sequence_len; $i++) {
            for ($j = 1; $j < $this->sequence_len; $j++) {
                if ($seq[$j-1][1] > $seq[$j][1]) {
                    list($seq[$j], $seq[$j-1]) = array($seq[$j-1], $seq[$j]);
                }
            }
        }
        return $seq;
    }
}
$answer = new Answer;
$answer -> getAnswer();


Measured memory_bytes: 9440
islands, requests = map(int, input().split(" "))
req = []
for r in range(requests):
    a, b = map(int, input().split(" "))
    req.append([a, b])
req = sorted(req, key = lambda x:x[1])
answer = 1
temp_end = req[0][1]
for r in req:
    if r[0] >= temp_end:
        temp_end = r[1]
        answer += 1
print(answer)

Measured memory_bytes: 63320
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define fill(x,v) memset(x, v, sizeof(x))
#define PI (ld)acos(-1)
#define endl '\n'
#define dbg(x) cout<<#x<<"="<<(x)<<endl;
#define dbg2(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl; 
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define IO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const ld eps=(ld)1e-9;
const ll inf=(ll)1e18;
const ll mod=(ll)1e9+7;
int n,m;
int d[1001][1001];
char a[1001][1001];
void f(){
	for (int i = 1; i < n+1; ++i)
	{
		if(a[i][1]=='.'){
			d[i][1]=1;
		}
		else break;
	}

	for (int i = 1; i < m+1; ++i)
	{
		if(a[1][i]=='.')
			d[1][i]=1;
		else break;
	}
	for (int i = 2; i <=n; ++i)
	{
		for (int j = 2; j <=m; ++j)
		{
			if(a[i][j]=='#'){
				d[i][j]=0;
			}
			else{
				d[i][j]=d[i-1][j]+d[i][j-1];
				d[i][j]%=mod;
			}
			// dbg(d[i][j]);
		}
	}
	cout<<d[n][m];

}


void solve(){
	cin>>n>>m;
	string s;
	for (int i = 1; i < n+1; ++i)
	{
		cin>>s;
		for (int j = 1; j < m+1; ++j)
		{
			a[i][j]=s[j-1];
		}
	}
	fill(d,0);
	f();
}

int main(){fio;
int test=1;
// cin>>test;
while(test--){
	solve();
	cout<<endl;
}
return 0;
}

Measured memory_bytes: 5120
S = list(input())
N = len(S)
R1 = [0]
L1 = []
R2 = []
L2 = []
mae = ""
output = [0]*N

for i in range(N):
    if S[i]=="R" and mae == "L":
        R1.append(i)
        L2.append(i-1)
    if S[i]=="L" and mae == "R":
        L1.append(i)
        R2.append(i-1)
    mae = S[i]
L2.append(N-1)
#
# print(R1)
# print(R2)
# print(L1)
# print(L2)

for i in range(len(R2)):
    cand = L2[i]-R1[i]+1
    if (R2[i]-R1[i])%2==1 and (L2[i]-R2[i])%2==1:
        output[R2[i]]=(R2[i]-R1[i]+1)//2 + (L2[i]-R2[i]-1)//2
        output[L1[i]]=(R2[i]-R1[i]+1)//2 + (L2[i]-R2[i]+1)//2
    elif (R2[i]-R1[i])%2==0 and (L2[i]-R2[i])%2==0:
        output[R2[i]]=(R2[i]-R1[i]+2)//2 + (L2[i]-R2[i])//2
        output[L1[i]]=(R2[i]-R1[i])//2 + (L2[i]-R2[i])//2
    elif (R2[i]-R1[i])%2==1 and (L2[i]-R2[i])%2==0:
        output[R2[i]]=(R2[i]-R1[i]+1)//2 + (L2[i]-R2[i])//2
        output[L1[i]]=(R2[i]-R1[i]+1)//2 + (L2[i]-R2[i])//2
    elif (R2[i]-R1[i])%2==0 and (L2[i]-R2[i])%2==1:
        output[R2[i]]=(R2[i]-R1[i]+2)//2 + (L2[i]-R2[i]-1)//2
        output[L1[i]]=(R2[i]-R1[i])//2 + (L2[i]-R2[i]+1)//2

outputstr = ""
for i in range(N-1):
    outputstr += "{} ".format(output[i])
outputstr += "{}".format(output[N-1])

print(outputstr)

Measured memory_bytes: 13200
#include<bits/stdc++.h>
using namespace std;
int N,M;
int a[100000];
int b[20][100001];
int dp[(1<<20)];
int main(){
  scanf("%d %d",&N,&M);
  for(int i=0;i<N;i++){
    scanf("%d",&a[i]);
    a[i]--;
    b[a[i]][i+1]++;
  }
  for(int i=0;i<M;i++)
    for(int j=0;j<N;j++)
      b[i][j+1]+=b[i][j];
  fill(dp,dp+(1<<M),1e9);
  dp[0]=0;
  for(int S=0;S<(1<<M);S++){
    int p=0;
    for(int i=0;i<M;i++)
      if(S>>i&1)p+=b[i][N];
    for(int i=0;i<M;i++){
      if(S>>i&1)continue;
      int cnt=b[i][N];
      int cost=cnt-(b[i][p+cnt]-b[i][p]);
      dp[S+(1<<i)]=min(dp[S+(1<<i)],dp[S]+cost);
    }
  }
  printf("%d\n",dp[(1<<M)-1]);
  return 0;
}

Measured memory_bytes: 15416
/*
─────────────────────
───────────████████──
──────────███▄███████
──────────███████████
──────────███████████
──────────██████─────
──────────█████████──
█───────███████──────
██────████████████───
███──██████████──█───
███████████████──────
███████████████──────
─█████████████───────
──███████████────────
────████████─────────
─────███──██─────────
─────██────█─────────
─────█─────█─────────
─────██────██────────
─────────────────────
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define int long long
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define reads(s) string s; cin >> s;
#define readarr(a, n) int a[(n) + 1] = {}; fori (i, 1, n) {cin >> a[i];}
#define readmat(a, n, m) int a[(n) + 1][(m) + 1] = {}; fori (i, 1, n) {fori (j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) fori (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) fori (i, 1, n) {fori (j, 1, m) cout << a[i][j] << " "; cout << endl;}
#define all(v) v.begin(), v.end()
#define sz(s) (int)(s.size())
#define pb push_back
#define fi first
#define se second
#define rz resize
#define fori(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define setprec(x) cout << fixed << setprecision(x);
 
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair <int, int>> vpi;
typedef vector < vector <int> > vvi;
 
const int INF = 4e18;
const int mod = 1e9+7; 

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

    #ifndef ONLINE_JUDGE 
        freopen ("INPUT.txt" , "r" , stdin);
        freopen ("OUTPUT.txt" , "w" , stdout);
        freopen ("OUTPUT_ERROR.txt" , "w" , stderr);
    #endif

    //start from here

    readb(n, k) readarr(a, n)

    int dp[n+1][k+1] = {};
    int count[n+1][k+1] = {};

    fori (i, 0, n) dp[i][0] = 1;

    count[0][0] = dp[0][0];
    fori (j, 1, k) count[0][j] = (count[0][j-1] + dp[0][j]) % mod;

    fori (i, 1, n)
    {
        fori (j, 1, k) 
        {
            if(j > a[i]) dp[i][j] = (count[i-1][j] - count[i-1][j - a[i]-1] + mod) % mod;
            else dp[i][j] = count[i-1][j];
        }

        count[i][0] = dp[i][0];
        fori (j, 1, k) count[i][j] = (count[i][j-1] + dp[i][j]) % mod;
    }

    print(dp[n][k])

    return 0;
}

Measured memory_bytes: 161336
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  ll a,b;
  cin>>a>>b;
  if(a>b){
    ll tmp = a;
    a = b;
    b = tmp;
  }
  //素因数分解
  vector<ll> v;
  vector<bool> prime_count(100000000,false);
  v.push_back(1);
  ll n = a;
  for(ll i = 2; i < sqrt(n)+2; i++){
    if(a%i!=0){
      continue;
    }
    else{
      while(a%i==0){
        if(!prime_count[i]){
          prime_count[i]=true;
          v.push_back(i);
          a/=i;
        }
        else{
          a/=i;
        }
      }
    }
    
    if(a==1) break;  
  }
  if(a>1)v.push_back(a);
  // for(int i = 0; i<v.size(); i++) cout<<v[i]<<endl;
  ll cnt = 0;
  for(int i = 0; i < v.size(); i++){
    if(b%v[i]==0){
      cnt++;
    }
  }
  //debug
  
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 12416
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

x = i()
if x == 0:
    print(1)
else:
    print(0)

Measured memory_bytes: 72644
#include <cstdio>
#include <utility>
#include <vector>
#include <climits>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_in(int c){int n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in(gcu());}
_sc(int &n){int c=gcu();return c==EOF?false:(n=in(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
//_sc(string &s){int c;s="";
//	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
template <typename H,typename... T> _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
template <typename T>
_vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
//_vo(string &s){for (char c: s) pcu(c);}
template <typename H,typename... T> _vo(H&& h, T&&... t){out(h);out(move(t)...);}
//template <typename T> _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
_vl(){out('\n');}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

int main() {
	for (int n; (n = in());) {
		vector<vector <int>> v(10, vector<int>(10, INT_MAX/2));
		int s = 0;
		while (n--) {
			int a = in(), b = in();
			v[a][b] = v[b][a] = in();
			s = max(s, max(a, b));
		}
		s++;
		for (int i = 0; i < s; i++)
			v[i][i] = 0;
		for (int k = 0; k < s; k++)
			for  (int i = 0; i < s; i++)
				for (int j = 0; j < s; j++)
					v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
		int ri = 0, rm = INT_MAX;
		for (int i = 0; i < s; i++) {
			int m = 0;
			for (int j = 0; j < s; j++)
				m += v[i][j];
			if (m < rm)
				ri = i, rm = m;
		}
		outl(ri, ' ', rm);
	}
}


Measured memory_bytes: 2568
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	int n,l;
	std::cin >> n >> l;
	int sum = (2*l+n-1)*n/2;
	if(l<=0&&l>-n) {
		print(sum);
		return 0;
	}
	if(l>0) {
		print(sum-l);
		return 0;
	}
	print(sum-l-n+1);
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
	static void Main()
	{
		Console.ReadLine();
		var numbers = Array.ConvertAll(Console.ReadLine().Split(new[] { ' ' }), number => long.Parse(number));

		long allSum = numbers.Sum();

		long min = long.MaxValue;
		long sum = 0;
		for (var i = 0; i < numbers.Length - 1; ++i) {
			sum += numbers[i];
			min = Math.Min(Math.Abs(allSum - sum * 2), min);
		}

		Console.WriteLine(min);
	}
}


Measured memory_bytes: 32348
fun main(array: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }
    val all = Math.pow(3.0, n.toDouble()).toInt()
    var cnt = 0
    for(l in list) {
        if(l % 2 == 0) cnt++
    }
    val yobun = Math.pow(2.0, cnt.toDouble()).toInt()
    print(all - yobun)
}

Measured memory_bytes: 36412
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int t;
vector< vector<int> > A;
vector<int> c;
vector<int> d;
vector<int> f;

void dfsVisit(int u) {
    t++;
    d[u] = t;
    c[u] = 1;
    for(int i=0; i<A[u].size(); i++) {
        int v = A[u][i];
        if(c[v] == 0) dfsVisit(v);
    }
    t++;
    f[u] = t;
}

void dfs() {
    for(int u=0; u<n; u++) c[u] = 0;
    t = 0;
    for(int u=0; u<n; u++) {
        if(c[u] == 0) {
            dfsVisit(u);
        }
    }
}

int main() {
    cin >> n;
    A.resize(n);
    c.resize(n);
    d.resize(n);
    f.resize(n);

    for(int i=0; i<n; i++) {
        int u,k;
        cin >> u >> k;
        A[u-1].resize(k);
        for(int j=0; j<k; j++) {
            int v;
            cin >> v;
            A[u-1][j] = v-1;
        }
        sort(A[u-1].begin(), A[u-1].end());
    }

    dfs();
    for(int i=0; i<n; i++) cout << i+1 << " " << d[i] << " " << f[i] << endl;
}


Measured memory_bytes: 3088