akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int n;
  cin >> n;
  
  vector<int> cont(n);
  
  for(int i = 0 ; i < n ; i++){
    cin >> cont.at(i);
  }
  
  int ans = 0;
  
  for(int i = 0 ; i < n-1 ; i++){
    for(int j = i+1 ; j < n ; j++){
      ans += cont.at(i)*cont.at(j);
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
p = list(map(int,input().split()))
e = [0] * (n-k+1)

for i in range(k):
    e[0] += float(1/2 * (1 + p[i]))
for j in range(n-k):
    e[j+1] = e[j] + float(1/2 * (p[j+k]-p[j]))
print(max(e))


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

struct Edge{
  int to, cost;

  Edge(int t, int c = 0): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

};
using Graph = vector<vector<Edge>>;
void add_edge(Graph& graph, int u, int v, int cost = 0){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}

int lowlink_br(int u, int p, int& num, const Graph& G, VI& ord, VI& low){
  int res = 0;
  ord[u] = low[u] = num++;
  
  for(auto& e: G[u]){
	int to = e.to;
	if(to == p) continue;
	if(ord[to] < 0){
	  res += lowlink_br(to, u, num, G, ord, low);
	  low[u] = min(low[u], low[to]);
	  if(ord[u] < low[to])
		++res;
	}
	else{
	  low[u] = min(low[u], ord[to]);
	}
  }

  return res;
}

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

  int N, M;
  cin >> N >> M;

  Graph G(N);
  REP(i,M){
	int u, v;
	cin >> u >> v;
	--u;
	--v;
	add_edge(G, u, v);
  }

  int num = 0;
  VI ord(N,-1), low(N);
  cout << lowlink_br(0, -1, num, G, ord, low) << endl;
  
  return 0;
}


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

template <int64_t N>
class modint {
    int64_t x;
public:
    modint(int64_t x = 0) : x((x % N + N) % N) {}
    modint operator-() const { return modint(-x); }
    modint& operator+=(const modint& a) { if ((x += a.x) >= N) x -= N; return *this; }
    modint& operator-=(const modint& a) { if ((x += N - a.x) >= N) x -= N; return *this; }
    modint& operator*=(const  modint& a) { (x *= a.x) %= N; return *this; }
    modint operator+(const modint& a) const { return modint(*this) += a; }
    modint operator-(const modint& a) const { return modint(*this) -= a; }
    modint operator*(const modint& a) const { return modint(*this) *= a; }
    modint pow(int64_t t) const {
        if (not t) return 1;
        modint a = pow(t >> 1); a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime mod
    modint inv() const { return pow(N - 2); }
    modint& operator/=(const modint& a) { return (*this) *= a.inv(); }
    modint operator/(const modint& a) const { return modint(*this) /= a; }
    friend ostream& operator<<(ostream& os, const modint& m){ os << m.x; return os; }
};
const int64_t mod = 1e9 + 7;
using mint = modint<mod>;

int main(){
    int n, k; cin >> n >> k;
    vector<int> a(n); mint ans = 0;
    for (auto i = 0; i < n; i++) cin >> a[i];
    for (auto i = 0; i < n; i++) {
        mint b = 0, c = 0;
        for (auto j = 0; j < n; j++) {
            if(a[i] > a[j]) b += 1;
            if(j > i and a[i] > a[j]) c += 1;
        }
        ans += c * k + b * k * (k - 1) / 2;
//        cout << i << " " << a[i] << " " << b << " " << c << " " << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

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

int main() { 
    int n, k, ans = 0;
    cin >> n >> k;
    int a[n], one;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        if(a[i] == 1) one = i;
    }
    int left = one;
    while(left > 0) {
        left -= k-1;
        ans++;
    }
    if(left != 0) one -= left;
    while(one < n-1) {
        one += k-1;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 640
use std::io::Write;

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn main() {
    let (n, h): (isize, isize) = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right().to_owned();
        let mut ws = s.split_whitespace();
        let a = ws.next().unwrap().parse().unwrap();
        let b = ws.next().unwrap().parse().unwrap();
        (a, b)
    };

    let mut a: Vec<isize> = Vec::new();
    let mut b: Vec<isize> = Vec::new();
    for _ in 0..n {
    let (a_i, b_i): (isize, isize) = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right().to_owned();
        let mut ws = s.split_whitespace();
        let a = ws.next().unwrap().parse().unwrap();
        let b = ws.next().unwrap().parse().unwrap();
        (a, b)
    };
        a.push(a_i);
        b.push(b_i);
    }

    let a_max = *a.iter().max().unwrap();
    b.sort_by(|x, y| y.cmp(x));

    let mut count = 0;
    let mut rest = h;
    for &b_i in &b {
        if b_i < a_max {
            break;
        }
        if rest <= 0 {
            break;
        }

        rest -= b_i;
        count += 1;
    }

    if rest <= 0 {
        println!("{}", count);
    } else {
        count += (rest + a_max - 1) / a_max;
        println!("{}", count);
    }
}


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

int H,W;
char A[10][10];

int nx,ny;
int gx,gy;

int main(){
    nx = 1;ny = 1;

    cin >> H >> W;
    for(int y = 1;y < H+1;y++){
        for(int x = 1;x < W+1;x++){
            cin >> A[x][y];
        }
    }

    gx = W;gy = H;
    A[1][1] = 'f';

    while(1){
 //       cout << nx << "," << ny << endl;

        if(A[nx+1][ny] == '#'){
            A[nx+1][ny] = 'f';
            nx = nx + 1;
            continue;
        }

        if(A[nx][ny+1] == '#'){
            A[nx][ny+1] = 'f';
            ny = ny + 1;
            continue;
        }

        break;
    }

    /*for(int y = 1;y < H+1;y++){
        cout << endl;
        for(int x = 1;x < W+1;x++){
            cout << A[x][y];
        }
    }*/

    for(int y = 1;y < H+1;y++){
        for(int x = 1;x < W+1;x++){

            if(A[x][y] == '#'){
                cout << "Impossible" << endl;
                exit(0);
            }

        }
    }

    cout << "Possible" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1 << 20);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int> > adj[MAX];

void D(){
  int i, j;
  priority_queue<pair<int, int> > PQ;
  int color[MAX];
  int d[MAX];
  for(i=0;i<n;i++){
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0] = 0;
  PQ.push(make_pair(0, 0));
  color[0] = GRAY;
  while(!PQ.empty()){
    pair<int, int> f = PQ.top();
    PQ.pop();
    int u = f.second;
    color[u] = BLACK;
    if(d[u] < f.first * (-1) )continue;

    for(j=0;j<adj[u].size();j++){
      int v = adj[u][j].first;
      if(color[v] == BLACK)continue;
      if(d[v] > d[u]+adj[u][j].second){
	d[v] = d[u] + adj[u][j].second;
	PQ.push(make_pair(d[v]*(-1), v) );
	color[v] = GRAY;
      }
    } // end for    
  } // end while 

  for(i=0;i<n;i++)cout << i << " " << (d[i] == INFTY?-1:d[i]) << endl;
  
}

int main(){
  int k, u, v, c;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> u >> k;
    for(int j=0;j<k;j++){
      cin >> v >> c;
      adj[u].push_back(make_pair(v, c) );
    }
  }
  D();   

  return 0;
}



Measured memory_bytes: 8000
import numpy as np
H,W,D = map(int,input().split())
SUM = H*W
px = np.zeros(SUM+1)
py = np.zeros(SUM+1)
for i in range(1,H+1):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        px[A[j]] = i
        py[A[j]] = j + 1

d = np.zeros(SUM+1)
for t in range(D+1,SUM+1):
    d[t] = d[t-D] + abs(px[t] - px[t-D])+ abs (py[t] - py[t-D]);
        
Q = int(input())
L = []
R = []
for i in range(Q): 
    l,r = map(int, input().split())
    print(int(d[r]-d[l]))

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define forup(i,a,b) for(int i=(a); i<(b); ++i)
#define fordn(i,a,b) for(int i=(a); i>(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)

#define gi(x) scanf("%d",&x)
#define gl(x) cin>>x
#define gd(x) scanf("%lf",&x)
#define gs(x) scanf(" %s",x)

#define D(x) cout << #x << " : " << x << endl

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

const int inf=numeric_limits<int>::max();
const LL linf=numeric_limits<LL>::max();

const int max_n=100001;

int n, a[max_n][3], dp[max_n][3];

int f(int day, int choice){
    if(dp[day][choice])
        return dp[day][choice];

    if(day == n-1)
        return dp[day][choice] = a[day][choice];

    switch(choice){
        case 0: return dp[day][0] = a[day][0] + max(f(day+1, 1), f(day+1, 2));
        case 1: return dp[day][1] = a[day][1] + max(f(day+1, 2), f(day+1, 0));
        case 2: return dp[day][2] = a[day][2] + max(f(day+1, 0), f(day+1, 1));
    }
}

int main() {
    // int a, b, c;
    gi(n);
    rep(i,n){
        gl(a[i][0]>>a[i][1]>>a[i][2]);
    }
    cout << max(f(0,0),max(f(0,1),f(0,2))) << endl;
    return 0;
}

Measured memory_bytes: 7296
// 基本テンプレート
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    string s; cin >> s;
    
    int N = s.length();

    int cnt = 0, ans = 0;
    for(int i=0; i<N; i++) {
        if(s[i] == 'W') {
            cnt++;
            ans += (i - cnt + 1);
        }
    }
    cout << ans << endl;
    return 0;
}


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

int N;
long long K;
std::vector<int> A;
std::map<int, int> city_to_j;
bool is_in_circle = false;

int main() {
  std::cin >> N >> K;
  A.assign(N, 0);
  int current_city = 0;
  int sta_j = 0;

  for (int i = 0; i < N; i++) {
    std::cin >> A[i];
    --A[i];
  }
  int div = 0;
  for (long long j = 0; j < K ; j++) {
    city_to_j[current_city] = j;
    if (city_to_j.count(A[current_city]) == 1) {
      div = j - city_to_j[A[current_city]] + 1;
      sta_j = city_to_j[A[current_city]];
      is_in_circle = true;
      current_city = A[current_city];
      break;
    }
    current_city = A[current_city];
  }
  if (is_in_circle) {
    for (int k = 0; k < ((K - sta_j) % div); k++) {
      current_city = A[current_city];
    }
    std::cout << current_city + 1 << std::endl;
  } else {
    std::cout << current_city + 1 << std::endl;
  }
}

Measured memory_bytes: 11256
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define all(obj) (obj).begin(), (obj).end()
#define lpair pair<ll, ll>
#define vint vector<ll>
#define vinput(name) for(int i=0; i<(int)(name.size()); i++) cin >> name[i];
#define voutput(name) for(int i=0; i<(int)(name.size()); i++) cout << name[i] << endl;
typedef long long ll;

using namespace std;

ll ans = 0;

int main(void){
	int n; cin >> n;
	string s; cin >> s;
	vint R, G, B;
	rep(i, n){
		if(s[i] == 'R') R.push_back(i+1);
		if(s[i] == 'G') G.push_back(i+1);
		if(s[i] == 'B') B.push_back(i+1);
	}



	ll ans = R.size() * G.size() * B.size();
	rep(i, n){
		for(int j=1; i-j >= 0 && i+j<n; j++) {
			if(s[i-j] != s[i] && s[i+j] != s[i] && s[i-j] != s[i+j]) {
				ans--;
			}
		}
	}


	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
n,y=(int(i) for i in input().split())
#print(n,y)

flag=0
for a in range(n+1):
  for b in range(n+1):
    c=n-a-b
    if 10*a+5*b+c==y/1000 and c>=0 and flag==0:
      flag=1
      print(str(a)+' '+str(b)+' '+str(c))

if flag==0:
      print(str(-1)+' '+str(-1)+' '+str(-1))

Measured memory_bytes: 3188
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int h, w, n;
	char[][] map, tempMap;
	boolean[][] deleteMap;
	
	void dropBlock() {
		for (int ii = 0; ii <= h; ii++) {
			for (int i = h; i >= 2; i--) {
				for (int j = 1; j <= w; j++) {
					if (tempMap[i][j] == '.' && tempMap[i-1][j] != '.') {
						tempMap[i][j] = tempMap[i-1][j];
						tempMap[i-1][j] = '.';
					}
				}
			}
		}
	}
	
	void addDeleteTarget(int y, int x, int dir) {
		if (dir == 0) {
			for (int i = 0; i < n; i++) {
				deleteMap[y][x+i] = true;
			}
		} else {
			for (int i = 0; i < n; i++) {
				deleteMap[y+i][x] = true;
			}
		}
	}
	
	boolean blockDeleted() {
		boolean blockLeft = false;
		boolean deletable = false;	
		
		dropBlock();
		/*
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				System.out.print(tempMap[i][j]);
			}
			System.out.println();
		}
		System.out.println();
		*/
		
		for (int i = 1; i <= h; i++) {
			Arrays.fill(deleteMap[i], false);
		}
		
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				char next = tempMap[i][j];
				if (next == '.') continue;
				else blockLeft = true;
				
				for (int k = 1; k < n; k++) {
					if (tempMap[i][j+k] != next) break;
					else if (k == n - 1) { 
						deletable = true;
						addDeleteTarget(i, j, 0);
					}
				}
				
				for (int k = 1; k < n; k++) {
					if (tempMap[i+k][j] != next) break;
					else if (k == n - 1) { 
						deletable = true;
						addDeleteTarget(i, j, 1);
					}
				}
			}
		}
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				if (deleteMap[i][j]) tempMap[i][j] = '.';
			}
		}
		
		if (blockLeft) {
			if (deletable) {
				return blockDeleted();
			} else {
				return false;
			}
		} else {
			return true;
		}
	}
	
	void swap(int y, int x, int yy, int xx) {
		char temp = map[y][x];
		map[y][x] = map[y+yy][x+xx];
		map[y+yy][x+xx] = temp;
	}
	
	void copyMap() {
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				tempMap[i][j] = map[i][j];
			}
		}
	}
	public void run() {
		boolean flag = false;
		Scanner in = new Scanner(System.in);
		h = in.nextInt();
		w = in.nextInt();
		n = in.nextInt();
		map = new char[h+2][w+2];
		tempMap = new char[h+2][w+2];
		deleteMap = new boolean[h+2][w+2];
		
		for (int i = 0; i <= h + 1; i++) {
			String s = "";
			if (i != 0 && i != h + 1)
				s = in.next();
			for (int j = 0; j <= w + 1; j++) {
				if (i == 0 || i == h + 1 || j == 0 || j == w + 1) 
					map[i][j] = 0;
				else
					map[i][j] = s.charAt(j - 1);
			}
		}
		end:
			for (int i = 1; i <= h; i++) {
				for (int j = 1; j <= w; j++) {
					if (map[i][j] != 0 && map[i][j+1] != 0) {
						swap(i, j, 0, 1);
						copyMap();
						if (blockDeleted()) {
							flag = true;
						}
						swap(i, j, 0, 1);
					}
					if (flag) break end;
				}
			}
		
		if (flag) System.out.println("YES");
		else System.out.println("NO");
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 21476
#include<bits/stdc++.h>
    #define sz(a) (int)(a).size()
     
    using namespace std;
     
    template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
    template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
    const int INF = 2e5+2;
    const long long hell = 998244353ll;
    

    int main(){
    	
    	ios_base::sync_with_stdio(0);cin.tie(0);
    	int a,b,c;
    	cin>>a>>b>>c;
    	cout<<(max(c-a+b,0))<<endl;

    #ifdef LOCAL_DEFINE
        cout << "Time elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif	
    	return 0;
    }

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	ch := s[len(s)-1]
	if ch == '3' {
		fmt.Println("bon")
	} else if ch == '0' || ch == '1' || ch == '6' || ch == '8' {
		fmt.Println("pon")
	} else {
		fmt.Println("hon")
	}
}


Measured memory_bytes: 1756
#include<bits/stdc++.h>
const int P=1e9+7;
int n,m,ans=0;
int f[6111][2];
int fix(int x){return x-=P,x+(x>>31&P);}
int main(){
	scanf("%d%d",&n,&m);
	n*=2;
	for(int i=0;i<=n;i+=2)f[i][!i]=1;
	for(int i=0;i<m;++i){
		for(int j=1;j<n;j+=2){
			f[j][0]=fix(f[j-1][0]+f[j+1][0]);
			f[j][1]=fix(f[j-1][1]+f[j+1][1]);
		}
		f[1][1]=(f[1][1]+f[1][0])%P;
		f[1][0]=0;
		for(int j=2;j<n;j+=2){
			f[j][0]=fix(f[j-1][0]+f[j+1][0]);
			f[j][1]=fix(f[j-1][1]+f[j+1][1]);
		}
		f[n][0]=f[n-1][0];
		f[n][1]=f[n-1][1];
		f[0][1]=f[1][1];
	}
	for(int i=0;i<=n;i+=2)ans=fix(ans+f[i][1]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
ll func2(ll *p, ll *q, ll *r, int A, int B, int C, int X, int Y)
{
    ll ans(0);
    ll max;
    int i(0);
    int x = X, y = Y, a = A, b = B, c = C;
    while (i++ < X + Y)
    {
        if (x && y)
        {
            max = p[a] > q[b] ? p[a] : q[b];
            max = max > r[c] ? max : r[c];
        }
        else if (x == 0 && y == 0)
            max = r[c];
        else if (x == 0)
            max = q[b] > r[c] ? q[b] : r[c];
        else if (y == 0)
            max = p[a] > r[c] ? p[a] : r[c];
        // cout << max << endl;
        ans += max;
        if (max)
        {
            if (max == p[a])
                --a, --x;
            else if (max == q[b])
                --b, --y;
            else if (max == r[c])
                --c;
        }
    }
    return ans;
}
void func()
{
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    ll p[A + 1], q[B + 1], r[C + 1];
    p[0] = 0;
    q[0] = 0;
    r[0] = 0;
    rep(i, 0, A) cin >> p[i + 1];
    rep(i, 0, B) cin >> q[i + 1];
    rep(i, 0, C) cin >> r[i + 1];
    sort(&p[0], &p[A + 1]);
    sort(&q[0], &q[B + 1]);
    sort(&r[0], &r[C + 1]);
    // rep(i, 0, A + 1) cout << p[i] << ' ';
    // cout << endl;
    // rep(i, 0, B + 1) cout << q[i] << ' ';
    // cout << endl;
    // rep(i, 0, C + 1) cout << r[i] << ' ';
    // cout << endl;
    ll ans = func2(p, q, r, A, B, C, X, Y);
    cout << ans << endl;
}
int main()
{
    func();
}

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

int main(){
	int N, K;
	cin >> N >> K;
	if(K > (N - 1) * (N - 2) / 2){
		cout << - 1 << endl;
	}else{
		cout << N - 1 + ((N - 1) * (N - 2) / 2 - K) << endl;
		for(int i = 2; i <= N; i++) cout << 1 << " " << i << endl;
		int cnt = 0;
		for(int i = 2; i <= N; i++){
			for(int j = i + 1; j <= N; j++){
				if(cnt == ((N - 1) * (N - 2) / 2) - K) return 0;
				cout << i << " " << j << endl;
				cnt++;
			}
		}
	}
	return 0;
}


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


int main(){
    ll h,w,n;
    cin >> h >> w >> n;
    map<pair<ll,ll>,ll> mp;
    for(ll i=0;i<n;i++){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        for(ll j=0;j<3;j++){
            for(ll k=0;k<3;k++){
                if(a-j>=0&&b-k>=0&&a-j<h-2&&b-k<w-2){
                    mp[make_pair(a-j,b-k)]++;
                }
            }
        }
    }
    vector<ll> res(10,0);
    for(auto p:mp){
        res[p.second]++;
    }
    ll count=0;
    for(ll i=1;i<=9;i++){
        count+=res[i];
    }
    res[0]=(h-2)*(w-2)-count;
    for(ll i=0;i<10;i++){
        cout << res[i] << endl;
    }
}


Measured memory_bytes: 59852
#include<iostream>
#include<map>
#include<cstdlib>
#include<string>
#define all(c) (c).begin(),(c).end()
using namespace std;
typedef pair<int,int> P;
int main(){
	int x,y;
	char c;
	string s;
	map<int,int> box,arr;
	map<int,int>::iterator ite;
	while(getline(cin,s),s.size()!=0){
		x=atoi(s.c_str());
		if(box.find(x)==box.end())
			box.insert(P(x,1));
		else
			box[x]++;
		
	}
	while(getline(cin,s),s.size()!=0){
		x=atoi(s.c_str());
		if(box.find(x)!=box.end()){
			if(arr.find(x)!=arr.end())
				arr[x]++;
			else{
				arr.insert(P(x,1+box[x]));
			}
		}
		
	}
	for(ite=arr.begin();ite!=arr.end();ite++)
		cout<<ite->first<<' '<<ite->second<<endl;
	return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<set>
using namespace std;

int main(){
    long n,a[200000],b[200001],x,ans=0,l,r;
    multiset<long> s;
    scanf("%ld",&n);
    for(long i=0;i<n;i++){
        scanf("%ld",&a[i]);
        b[a[i]]=i;
    }
    s.insert((long)-1);
    s.insert(n);
    for(long i=1;i<=n;i++){
        set<long>::iterator itr=s.lower_bound(b[i]);
        r=*itr;
        l=*(--itr);
        x=(b[i]-l)*(r-b[i]);
        ans+=x*i;
        s.insert(b[i]);
    }
    printf("%ld\n",ans);
}

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

using namespace std;

int main() {
    int a[210], N, count = 0;
    bool flg=false;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    while (true){
        for (int i = 0; i < N; i++) {
            if (a[i] % 2 != 0) {
                flg =true;
            }
        }
        if(flg) break;
        for (int i = 0; i < N; i++) {
            a[i] /= 2;
        }
        count++;
    }
    cout << count<< endl;
    return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    S[K-1] = char((S[K-1] - 'A') + 'a');
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String s = sc.next();
        String t = sc.next();

        if(s.length() < t.length()){
            System.out.println("UNRESTORABLE");
            return;
        }

        for(int head = s.length() - t.length(); head >= 0; --head){
            if(isEqualOrLike(s.substring(head, head + t.length()), t)){
                System.out.println(buildAns(head, s, t));
                return;
            }
        }

        System.out.println("UNRESTORABLE");        
    }

    static boolean isEqualOrLike(String s, String t){
        if(s.length() != t.length()) return false;

        for(int i = 0; i < s.length(); ++i){
            char cs = s.charAt(i);
            if(cs == '?') continue;

            char ct = t.charAt(i);
            if(cs != ct) return false;
        }
        return true;
    }

    static String buildAns(int head, String s, String t){
        StringBuilder sb = new StringBuilder(s.length());
        for(int i = 0; i < s.length(); ++i){
            if(head <= i && i < head + t.length()) sb.append(t.charAt(i - head));
            else sb.append((s.charAt(i) == '?') ? 'a' : s.charAt(i));
        }
        return sb.toString();
    }
}

Measured memory_bytes: 23764
if __name__ == "__main__":
    n = int(input())
    nums = [int(s) for s in input().split()]
    odds = [0]        
    for num in nums[::2]:
        odds.append(num + odds[-1])
    
    res = [0]
    for i, num in enumerate(nums[1::2]):
        res.append(max(res[-1]+num, odds[i+1]))
    
    if n % 2 == 0:
        print(res[-1])
    else:
        ans = float('-inf')
        for i, r in enumerate(res):
            ans = max(ans, res[i] + odds[-1] - odds[i+1])
        print(ans)



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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a - b >= c){
        cout << 0 << endl;
    }else{
        cout << c - (a - b) << endl;
    }
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto abc = readln.split.to!(int[]);
    auto A = abc[0];
    auto B = abc[1];
    auto C = abc[2];
    writeln((A < C && C < B) || (B < C && C < A) ? "Yes" : "No");
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <numeric>
#include <map>
using namespace std;

int main()
{
    int N;
    cin >> N;
    map<string, int> M;
    for (int i = 0; i < N; ++i)
    {
        string Si;
        cin >> Si;
        M[Si] = 1;
    }
    cout << M.size() << endl;
    return 0;
}

Measured memory_bytes: 19204
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    a = A.pop(0)
    ans = a-1
    b = 2
    for a in A:
        if b == a:
            b += 1
        c = (a-1) // b
        ans += c
    return ans


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  double n; cin >> n;
  vector<int> x(n);
  for (int i = 0; i < n; i++) cin >> x[i];
  int p = round(accumulate(x.begin(), x.end(), 0) / n);
  int res = 0;
  for (auto &i : x) {
    res += pow(p - i, 2);
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
int i,j;
scanf("%d %d",&i,&j);
if ((i==1 && j==2) || (i==2 && j==1))
  printf("3");
else if ((i==1 && j==3) || (i==3 && j==1))
  printf("2");
else
  printf("1");
}

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

 
int main() {
    int n;
    cin >> n;
    if(n%1000 == 0) cout << 0 << endl;
    else cout << 1000 - n%1000 << endl;

}


Measured memory_bytes: 3632
#include <iostream>
#include <cstring>

using namespace std;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)

int a[1005][1005];
int dp[1005][1005]; // dp[i][j] := N-1???????????§???(i, j)??????????????£??????

int main()
{
	int H, W, N;
	
	while (cin >> H >> W >> N, H) {
		memset(dp, 0, sizeof dp);

		rep(i, H) rep(j, W) cin >> a[i][j];

		dp[0][0] = N - 1;

		rep(i, H) rep(j, W) {
			if (i == 0 && j == 0) continue;

			if (i - 1 >= 0) {
				bool f = (dp[i - 1][j] % 2 == 0 ? a[i - 1][j] : !a[i - 1][j]) == 0;
				dp[i][j] += (f ? (dp[i - 1][j] / 2) : (dp[i - 1][j] + 1) / 2);
			}

			if (j - 1 >= 0) {
				bool f = (dp[i][j - 1] % 2 == 0 ? a[i][j - 1] : !a[i][j - 1]) == 1;
				dp[i][j] += (f ? dp[i][j - 1] / 2 : (dp[i][j - 1] + 1) / 2);
			}
		}

		rep(i, H) rep(j, W) {
			a[i][j] ^= dp[i][j] % 2;
		}

		int y = 0, x = 0;

		while (y < H && x < W) {
			(a[y][x] ? x : y)++;
		}

		cout << y + 1 << ' ' << x + 1 << endl;
	}
}

Measured memory_bytes: 10948
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;
const int64_t MOD = 1000000007;

int64_t fac[MAX], finv[MAX], inv[MAX];
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

int64_t COM(int n, int k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
  int64_t N, K, ma = 0, mi = 0;
  cin >> N >> K;
  vector<int64_t> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }
  COMinit();
  sort(A.begin(), A.end());
  for (int i = K - 1; i < N; i++)
  {
    ma = (ma + (A.at(i) * COM(i, K - 1)) % MOD) % MOD;
  }
  for (int i = 0; i < N - (K - 1); i++)
  {
    mi = (mi + (A.at(i) * COM((N - (i + 1)), K - 1)) % MOD) % MOD;
  }
  cout << (ma - mi + MOD) % MOD << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
vector<int> g[N];
int dp[N][2];
int vis[N][2];
int dfs(int u, int p, int color){
	if(vis[u][color]) return dp[u][color];
	vis[u][color]=1;
	// if((p && sz(g[u])==1)||sz(g[u])==0){
	// 	dp[u][color] = 1;
	// 	return 1;
	// }
	int ans = 1;
	if(color==0){
		for(auto j:g[u]){
			if(j!=p)
				ans = (ans*(dfs(j,u,color)+dfs(j,u,!color))%M)%M;
		}
	}
	else{
		for(auto j:g[u]){
			if(j!=p)
				ans = (ans*dfs(j,u,!color))%M;
		}
	}
	// trace(u,color,ans);
	dp[u][color] = ans;
	return ans;
}
signed main()
{
	ios_base::sync_with_stdio(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{   
		int n;
		cin >> n;
		rep(i,0,n-1){
			int a,b;
			cin >> a >> b;
			g[a].pb(b);
			g[b].pb(a);
		}	
		cout<<(dfs(1,0,1)+dfs(1,0,0))%M;
	}
}

Measured memory_bytes: 39936
#include <stdio.h>
#include <string.h>
int main(void){
    // Your code here!
    char s[1000];
    int k, n, i;
    
    scanf("%d",&k);
    scanf("%s",s);
    
    n=strlen(s);
    
    if(n<=k) printf("%s\n",s);
    
    else{
        for(i=k;i<k+3;i++) s[i]='.';
        s[i]='\0';
        printf("%s\n",s);
    }
    return 0;
}

Measured memory_bytes: 1644
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF 9999999
#define SOUR 400
#define SINK 401
#define NW	 402
#define NC	 403
#define NM	 404
#define NW2	 405
#define NC2  406
#define NM2	 407

class Node
{
public:
	vector<int> to;
};

int flow[410][410],capa[410][410];

int dfs(int p, int T, int mf, vector<Node>& graph, vector<int>& level, vector<bool>& finished)
{
	if(p==T) return mf;
	if(finished[p]) return 0;
	
	finished[p]=true;
	
	for(int i=0; i<graph[p].to.size(); i++)
	{
		int next=graph[p].to[i], fw=capa[p][next]-flow[p][next];
		if(level[p] >= level[next]) continue;
		if(fw <=0 ) continue;
	
		int f=dfs(next, T, min(mf, fw), graph, level, finished);
		if(f>0)
		{
			finished[p]=false;
			flow[p][next]+=f;
			flow[next][p]-=f;
			return f;
		}
	}
	
	return 0;
}

int dinic(int S, int T, vector<Node>& graph)
{
	bool end=false;
	int total=0;
	while(!end)
	{
		end=true;
		vector<int> level(graph.size(), -1);
		level[S]=0;
		
		queue<int> q;
		q.push(S);
		while(!q.empty())
		{
			int n=q.front(); q.pop();
			for(int i=0; i<graph[n].to.size(); i++)
			{
				int next=graph[n].to[i];
				if(level[next]!=-1) continue;
				if(capa[n][next]-flow[n][next] <= 0) continue;
				level[next]=level[n]+1;
				q.push(next);
			}
		}
		
		if(level[T]==-1) break;
		
		vector<bool> finished(graph.size());
		while(1)
		{
			int fw=dfs(S, T, INF, graph, level, finished);
			if(fw<=0) break;
			
			total+=fw;
			end=false;
		}
	}
	
	return total;
}

void Connect(int u, int v, int w, vector<Node>& graph)
{
	graph[u].to.push_back(v);
	graph[v].to.push_back(u);
	capa[u][v]+=w;
	capa[v][u]+=w;
	
	flow[v][u]+=w;
}

int main()
{
	int N[7];
	while(scanf("%d%d%d%d%d%d%d", &N[0],&N[1],&N[2],&N[3],&N[4],&N[5],&N[6]))
	{
		if(N[0]<0&&N[1]<0&&N[2]<0&&N[3]<0&&N[4]<0&&N[5]<0&&N[6]<0) break;
		
		memset(flow,0,sizeof(flow));
		memset(capa,0,sizeof(capa));
		vector<Node> graph(410);
		
		Connect(NW, NW2, N[4], graph);
		Connect(NC, NC2, N[5], graph);
		Connect(NM, NM2, N[6], graph);
		
		for(int i=0; i<N[0]; i++)
		{
			Connect(SOUR, 50*0+i, 1, graph);
			Connect(50*1+i,NW, 1, graph);
			Connect(50*0+i, 50*1+i, 1, graph);
		}
		
		for(int i=0; i<N[1]; i++)
		{
			Connect(50*3+i, NC, 1, graph);
			Connect(50*2+i, 50*3+i, 1, graph);
		}
		
		for(int i=0; i<N[2]; i++)
		{
			Connect(NW2, 50*4+i, 1, graph);
			Connect(50*5+i, NM, 1, graph);
			Connect(50*4+i, 50*5+i, 1, graph);
		}
		
		for(int i=0; i<N[3]; i++)
		{
			Connect(NC2, 50*6+i, 1, graph);
			Connect(50*7+i, SINK, 1, graph);
			Connect(50*6+i, 50*7+i, 1, graph);
		}
		Connect(NM2, SINK, N[6], graph);

		
		for(int i=1; i<4; i++)
		{
			for(int k=0; k<N[i]; k++)
			{
				int S,t;
				scanf("%d", &S);
				while(S--)
				{
					scanf("%d", &t); t--;

					Connect(50*((i-1)*2+1)+t, 50*(i*2)+k, 1, graph);

				}
			}
		}
		
		printf("%d\n", dinic(SOUR, SINK, graph));

	}
}

Measured memory_bytes: 2232
use std::collections::HashMap;

use proconio::{fastout, input, marker::Usize1};

struct UnionFind {
    pub parent: Vec<isize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut parent = vec![];
        let mut rank = vec![];
        for _ in 0..n {
            parent.push(-1);
            rank.push(0);
        }
        UnionFind { parent, rank }
    }

    fn is_root(&self, x: usize) -> bool {
        self.parent[x] < 0
    }

    fn find(&mut self, x: usize) -> usize {
        if self.is_root(x) {
            return x;
        }

        let root = self.find(self.parent[x] as usize);
        self.parent[x] = root as isize;
        root
    }

    fn unite(&mut self, x: usize, y: usize) {
        let rx = self.find(x);
        let ry = self.find(y);
        if rx == ry {
            return;
        }

        if self.rank[rx] < self.rank[ry] {
            self.parent[ry] += self.parent[rx];
            self.parent[rx] = ry as isize;
        } else {
            self.parent[rx] += self.parent[ry];
            self.parent[ry] = rx as isize;
            if self.rank[rx] == self.rank[ry] {
                self.rank[rx] += 1;
            }
        }
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    fn size(&mut self, x: usize) -> usize {
        let root = self.find(x);
        -self.parent[root] as usize
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        l: usize,
    }

    let mut road = UnionFind::new(n);
    for _ in 0..k {
        input! {
            p: Usize1,
            q: Usize1,
        }
        road.unite(p, q);
    }

    let mut train = UnionFind::new(n);
    for _ in 0..l {
        input! {
            r: Usize1,
            s: Usize1,
        }
        train.unite(r, s);
    }


    let mut map: HashMap<(usize, usize), usize> = HashMap::new();
    for i in 0..n {
        let count = map.entry((road.find(i), train.find(i))).or_insert(0);
        *count += 1;
    }

    for i in 0..n {
        print!("{}", map.get(&(road.find(i), train.find(i))).unwrap());
        if i == n - 1 {
            println!();
        } else {
            print!(" ");
        }
    }
}


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

using namespace std;


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define int long long

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second

#define mod 1000000007

template <typename T>
void print(T x)
{
	std::cout << x <<" " ;
}


template <typename T>
void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int N;
	cin >> N ;
	int tmp = N;
	map<int,int>mp;

	for (int x; tmp--; mp[x]++) {
		cin >> x;
	}

	if (mp.size() == N) {
		print("YES");
	}
	else {
		print("NO");
	}
	
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
    
#define int long long
    
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define FORR(i,m,n) for(int i=m;i>=n;i--)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 99999999999
#define MOD (int)(1e9)+7
    
using namespace std;
    
int dy[4]={1, 0, -1, 0};
int dx[4]={0, 1, 0, -1};
    
int32_t main(){
    int l;
    cin >> l;
    
    int r=0;
    while((1 << r+1) <= l) r++;

    int n = r+1;
    cout << n << " ";

    vector<int> fr, to, len;
    REP(i, r){
        fr.pb(i+1);
        to.pb(i+2);
        len.pb(0);

        fr.pb(i+1);
        to.pb(i+2);
        len.pb(1 << i);
    }

    for(int i=n-1; i>0; i--){
        if(l-(1 << (i-1))>=(1 << r)){
            fr.pb(i);
            to.pb(n);
            len.pb(l-(1 << (i-1)));
            l-=(1 << (i-1));
        }
    }

    cout << fr.size() << endl;
    REP(i, fr.size()){
        cout << fr[i] << " " << to[i] << " " << len[i] << endl;
    }
}

Measured memory_bytes: 256
while 1:
    n = int(input())
    if n == 0:
        break
    a = 0
    for i in range(1,n):
        b = 0
        for j in range(i,n):
            b += j
            if b >= n:
                break
        if b == n:
            a += 1
    print(a)


Measured memory_bytes: 5592
num = int(input())
lst = [i for i in range(1, num + 1)]

max, before = 0, -1
for l in lst:
  num, count = l, 0
  while num % 2 == 0:
    num /= 2
    count += 1
  if before < count:
    max, before = l, count 

print(max)

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int32_t main(){
	boost;

  	//code
	int n , m , x , y;
	cin >> n >> m;
	int a[n];
	vector<pair<int,int>> b;
	multiset<int> st;


	for(int i = 0 ; i < n ; ++i){
		cin >> a[i];
		st.insert(a[i]);
	}


	for(int i = 0 ; i < m ; ++i){
		cin >> x >> y;
		b.push_back({y,x});
	}

	sort(b.begin(),b.end());
	reverse(b.begin() , b.end());
	int s = 0;
	for(int i = 0 ; i < m ; ++i){
		auto idx = st.lower_bound(b[i].first);
		if(idx != st.begin()){
			while(*st.begin() < b[i].first and (b[i].second)--  and !st.empty()){
				st.erase(st.begin());
				s += b[i].first;
			}
		}
		else{
			break;
		}
	}
	for(auto i : st){
		s += i;
	}
	cout << s;
	return 0;
}


Measured memory_bytes: 7928
import sys
sys.setrecursionlimit(10**9)

def divisor(x):
    div=[]
    for i in xrange(1,int(x**0.5)+1):
        if x%i==0:
            div.append(i)
            if i!=x/i:
                div.append(x/i)
    return div

def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n/b)+n%b

n=int(raw_input())
s=int(raw_input())

if n==s:
    print(n+1)
    quit()

if n<s:
    print(-1)
    quit()

for i in xrange(2,int(n**0.5)+1):
    if f(i,n)==s:
        print(i)
        quit()

div=divisor(n-s)
div.sort()
for i in div:
    if f(i+1,n)==s:
        print(i+1)
        quit()
print(-1)

Measured memory_bytes: 16368
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		String clima = reader.nextLine();
		if(clima.equals("Sunny")) {
			System.out.println("Cloudy");
		}else if(clima.equals("Cloudy")) {
			System.out.println("Rainy");
		}else {
			System.out.println("Sunny");
		}
	}

}


Measured memory_bytes: 23252
n,m=gets.split.map(&:to_i)
l=[nil]
n.times do
  l << []
end
m.times do
  x,y,z=gets.split.map(&:to_i)
  l[x] << y
  l[y] << x
end
v=[0]*(n+1)
c=0
1.upto(n) do |i|
  next if v[i]==1
  c+=1
  s=[i]
  while s!=[]
    z=[]
    s.each do |j|
      l[j].each do |lj|
        if v[lj]==0
          v[lj]=1
          z << lj
        end
      end
    end
    s=z.dup
  end
end
puts c


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int a, b, c;
    cin >> a >> b >> c;
    if (c >= a && c <= b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	int w, h;
	char[][] c;
	int[] dx = {0, -1, 1, 0};
	int[] dy = {-1, 0, 0, 1};

	int f(int x, int y) {
		if (x < 0 || w <= x || y < 0 || h <= y || c[y][x] != '.') {
			return 0;
		}
		c[y][x] = '#';
		int res = 1;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			res += f(nx, ny);
		}
		return res;
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		while (true) {
			w = sc.nextInt();
			h = sc.nextInt();
			if ((w | h) == 0) {
				break;
			}

			c = new char[h][];
			for (int i = 0; i < h; i++) {
				c[i] = sc.next().toCharArray();
			}

			int sx = 0, sy = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (c[i][j] == '@') {
						sx = j;
						sy = i;
						c[i][j] = '.';
					}
				}
			}

			System.out.println(f(sx, sy));
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 26984
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

#define INF 10000000000

ll a, b, c, n, m, x, y, z, w, h, ans = 0, cnt = 0, mx = 0, mn = INF;
string s;

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

    cin >> n >> s;
    string left, right, tmp;
    rep(i, n - 1){
        left = s.substr(0, i + 1);
        right = s.substr(i + 1);
        cnt = 0;
        for(char j = 'a'; j <= 'z'; j++){
            if(left.find(j) != string::npos && right.find(j) != string::npos){
                cnt++;
            }
        }
        mx = max(mx, cnt);
    }
    cout << mx << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

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

		while(true){
			//縦と横のint型の変数
			int intHeight = scan.nextInt();
			int intWidth = scan.nextInt();

			//縦と横の長さがともに０の時ループを抜ける
			if(intHeight == intWidth && intHeight == 0){
				break;
			}
			//縦のループ
			for(int i = 0 ;i < intHeight;i++){
				//段数が奇数の時,＃から出力する
				if(i % 2 == 0){
					//横の出力
					for(int j = 0;j < intWidth;j++){
						if(j % 2 == 0){
							System.out.print("#");
						}else if(j % 2 == 1){
							System.out.print(".");
						}
					}
					System.out.println("");
				//段数が偶数の時,"."から出力する
				}else if(i % 2 == 1){
					for(int j = 0;j < intWidth;j++){
						if(j % 2 == 0){
							System.out.print(".");
						}else if(j % 2 == 1){
							System.out.print("#");
						}
					}
					System.out.println("");
				}
			}

			//AOZの制約のための空行
			System.out.println("");
		}
			scan.close();
	}
}



Measured memory_bytes: 32868
import math
from functools import reduce

K=int(input())

ans=K*(1+K)/2
for i in range(1, K+1):
    for j in range(i+1, K+1):
        ans+=math.gcd(i,j)*6
        for k in range(j+1,K+1):
            ans+=reduce(math.gcd, [i,j,k])*6
print(str(int(ans)))

Measured memory_bytes: 9588
import sys
import io

f = sys.stdin.buffer
n = int(f.readline())
h = list(map(int, f.readline().split()))
p0, p1 = 0, abs(h[1] - h[0])
for i in range(2, n):
    p2 = min(p1 + abs(h[i] - h[i - 1]), p0 + abs(h[i] - h[i - 2]))
    p0, p1 = p1, p2
print(p1)


Measured memory_bytes: 51696