akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define MOD 1000000007

ll mul(ll a, ll b) {
	ll x = (a * b) % MOD;
	if(x < 0) return x + MOD;
	return x;
}

ll maxProductSubarrayOfSizeK(ll A[], ll n, ll k) 
{  
	sort(A, A + n); 
	ll product = 1; 
	if (A[n - 1] == 0 && (k & 1)) 
		return 0; 
	if (A[n - 1] <= 0 && (k & 1)) { 
		for (ll i = n - 1; i >= n - k; i--) 
			product = mul(product, A[i]); 
		return product; 
	} 
	ll i = 0; 
	ll j = n - 1; 
	if (k & 1) { 
		product = mul(product, A[j]);
		j--; 
		k--; 
	} 
	k >>= 1;  
	for (ll itr = 0; itr < k; itr++) { 
		ll left_product = A[i] * A[i + 1]; 
		ll right_product = A[j] * A[j - 1]; 
		if (left_product > right_product) { 
			product = mul(product, left_product % MOD);
			i += 2; 
		} 
		else { 
			product = mul(product, right_product % MOD);
			j -= 2; 
		} 
	} 
	return product; 
} 

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

	ll n, k; cin >> n >> k;
	ll a[n];
	for(ll i = 0; i < n; i++)
		cin >> a[i];

	cout << maxProductSubarrayOfSizeK(a, n, k);

	return 0;
}

Measured memory_bytes: 5196
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = input().split()[0]

le = len(n)

po = 0

co = 0

for i in range(le-1,-1,-1):
    nu = int(n[i])
    nu += co
    if nu == 5:
        if i != 0 and int(n[i-1]) + 1 > 5:
            co = 1
        else:
            co = 0
        po += nu
    elif nu > 5:
        co = 1
        po += 10 - nu
    else:
        co = 0
        po += nu
print(po + co)

    






Measured memory_bytes: 5740
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

sx, sy, tx, ty = il()
a = ["U", "R", "D", "L"]
for i in [0, 2]:
    print(a[i] * (ty-sy), end="")
    print(a[i+1] * (tx-sx), end="")
for i in [0, 2]:
    print(a[(i+3)%4], end="")
    print(a[i] * (ty-sy+1), end="")
    print(a[i+1] * (tx-sx+1), end="")
    print(a[(i+2)%4], end="")

Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>
void swap(int *a,int *b);
int main(){
	char c,d,n;
	int cup[3]={1,0,0},i=5;
	while(scanf("%c,%c",&c,&d)!=EOF){
		swap(&cup[c-65],&cup[d-65]);
	}
	for(i=0;i<3;i++){
		if(cup[i]==1) printf("%c\n",i+65);
	}
	return 0;
}


void swap(int *a,int *b){
	int tmp; 
	tmp=*a;
	*a = *b;
	*b = tmp;
	return;
}
	

Measured memory_bytes: 976
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define endl "\n"

struct edge{
  ll to, cost;
  edge(){}
  edge(ll t, ll c){to = t; cost = c;}
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vector<vector<edge>> G(N, vector<edge>(0));
  for(int i = 0; i < N-1; i++){
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    G.at(a).push_back(edge(b, c));
    G.at(b).push_back(edge(a, c));
  }

  ll Q, K;
  cin >> Q >> K;
  K--;

  vll res(N, INF);
  priority_queue<Pll, vector<Pll>, greater<Pll>> que;
  que.push(Pll(K, 0));
  res.at(K) = 0;
  while(!que.empty()){
    ll v = que.top().first;
    ll c = que.top().second;
    que.pop();

    if(res.at(v) < c) continue;

    for(int i = 0; i < G.at(v).size(); i++){
      ll nextv= G.at(v).at(i).to;
      ll nextc = G.at(v).at(i).cost;
      if(res.at(nextv) < c + nextc) continue;
      res.at(nextv) = c + nextc;
      que.push(Pll(nextv, res.at(nextv)));
    }
  }
  vll ans(0);
  for(int i = 0; i < Q; i++){
    ll x, y;
    cin >> x >> y;
    x--; y--;
    ans.push_back(res.at(x) + res.at(y));
  }
  for(auto x: ans) cout << x << endl;
}

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

using namespace std;

int N, K;

void solve() {
    cin >> N >> K;
    vector<int> L(N);

    for (int i = 0; i < N; ++i) cin >> L[i];
    sort(L.begin(), L.end(), greater<int>());

    int ans = 0;
    for (int i = 0; i < K; ++i) ans += L[i];
    cout << ans << endl;
}

int main() {
    solve();
}

Measured memory_bytes: 256
n = int(input())
min_ = 0
list_ = set(list(map(int, input().split())))

while True:
  tmp = min(list_)
  list_ = set([i%tmp for i in list_])
  if 0 in list_:
    list_.remove(0)
  list_.add(tmp)
  if tmp==min(list_):
    break
print(tmp)

Measured memory_bytes: 20772
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = lc()
n = len(s)

fst = 0
lat = 0
ans = 0

if n % 2:
    fst = s[n//2::-1]
    lat = s[n//2:]
    ans = n//2 + 1

else:
    fst = s[n//2::-1]
    lat = s[n//2-1:]
    ans = n//2
  
for i in range(len(fst)-1):
    if fst[0] != lat[0]:
        break
    
    if fst[i+1] == fst[i] and lat[i+1] == lat[i]:
        ans += 1
        
    else:
        break
        
print(ans)

Measured memory_bytes: 4776
#include <stdio.h>

int main(void){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if(0<=a && a<=100 && 0<=b && b<=100 && 0<=c && c<=100){
      if(a<b && b<c){
        printf("Yes\n");
        }else{
            printf("No\n");
        }
  }
  return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int X[2], Y[2];

int main(void){
	//IO("test.in", "test.out");
	scanf("%d%d%d%d", &X[0], &Y[0], &X[1], &Y[1]);
	printf("%d %d %d %d\n", X[1] - (Y[1] - Y[0]), Y[1] + (X[1] - X[0]), X[0] - (Y[1] - Y[0]), Y[0] + (X[1] - X[0]));
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n){
    Int res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

Int gcd(Int a, Int b) {
    return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
    return a * b / gcd(a, b);
}
// a x + b y = gcd(a, b)
Int extgcd(Int a, Int b, Int &x, Int &y) {
    Int g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}



int main(){
    cin.tie(0);
    int N;
cin >> N;
if (N < 1000) cout << "ABC" << endl;
else cout << "ABD" << endl;
} 


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int N;

  string S;

  cin >> N ;
  cin >> S ;

  int ans=0;

  for(int i=0;i<N-2;i++){
    if(S.at(i)=='A'&&S.at(i+1)=='B'&&S.at(i+2)=='C') ans++;
  }

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

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
    long answer = 0;
		long n = long.Parse(Console.ReadLine());//int.Parseは文字列を整数に変換。
    long[][] vertexesRed = new long[n][];//x座標、y座標、使ったら1
    long[][] vertexesBlue = new long[n][];//x座標、y座標、使ったら1
    for(long i = 0; i < n; i++)
    {
      vertexesRed[i] = new long[3];
      vertexesBlue[i] = new long[2];
    }
    for(long i = 0; i < n; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
      vertexesRed[i][0] = nums[0];
      vertexesRed[i][1] = nums[1];
    }
    for(long i = 0; i < n; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
      vertexesBlue[i][0] = nums[0];
      vertexesBlue[i][1] = nums[1];
    }
    Array.Sort(vertexesRed, (a, b) => a[0].CompareTo(b[0]));//x座標でソート
    Array.Sort(vertexesBlue, (a, b) => a[0].CompareTo(b[0]));

    long[] maxMemo = new long[2];//番号とy座標

    for(long blueNum = 0; blueNum < n; blueNum++)
    {
    maxMemo[0] = -1;
    maxMemo[1] = -1;
      for(long redNum = 0; redNum < n; redNum++)
      {
        if(vertexesRed[redNum][0] < vertexesBlue[blueNum][0] &&
          vertexesRed[redNum][1] < vertexesBlue[blueNum][1] &&
          vertexesRed[redNum][1] > maxMemo[1] &&
          vertexesRed[redNum][2] == 0)
        {
          maxMemo[1] = vertexesRed[redNum][1];
          maxMemo[0] = redNum;
        }
      }
      //Console.WriteLine(maxMemo[0]+" "+maxMemo[1]);
      
      if(maxMemo[0] != -1)
      {
        vertexesRed[maxMemo[0]][2] = 1;
        answer++;
        //Console.WriteLine(maxMemo[0]+" "+maxMemo[1]);
      }
      
    }

		Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

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

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  
  vector<int> dp(n);
  dp[0] = 0; dp[1] = abs(h[1] - h[0]);
  
  for(int i = 2; i < n; i++){
    dp[i] = min(abs(h[i]-h[i-2]) + dp[i-2], abs(h[i]-h[i-1]) + dp[i-1]);
    //cout << dp[i] << endl;
  }
  if(n > 3){
  	cout << dp[n-1] << endl;
  }
  else{
    cout << dp[1] << endl;
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define N 100003
#define what_is(x) cerr << #x << " is " << x << endl;

using namespace std;

int main() {
	// for fast input output using cin cout
	std::ios_base::sync_with_stdio(false);

	// size of array
	// input
	int n;
	cin>>n;
	long long dp[100] = {0};
	dp[0] = 2;
	dp[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		dp[i] = dp[i-1] + dp[i-2];
	}

	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cout << fixed << setprecision(10);
    int N,K,C;
    string S;
    cin >> N >> K >> C >> S;
    int cnt = 0; //働いた日数
    int pnt = 0; //走査ポイント
    vector<int> frw(K,0);
    vector<int> rev(K,0);
    while(cnt<K&&pnt<N) {
        if(S.at(pnt)=='o') {
            frw.at(cnt) = pnt;
            cnt++;
            pnt+=(C+1);
        } else {
            pnt++;
        }
    }
    cnt = 0;
    pnt = N-1;
    while(cnt<K&&pnt>=0) {
        if(S.at(pnt)=='o') {
            rev.at(cnt) = pnt;
            cnt++;
            pnt-=(C+1);
        } else {
            pnt--;
        }
    }
    SORT(rev);
    rep(i,K) {
        if(frw.at(i)==rev.at(i)) {
            cout << frw.at(i)+1 << endl;
        }
    }
    // rep(i,K) {
    //     cout << frw.at(i) << endl;
    // }
    // rep(i,K) {
    //     cout << rev.at(i) << endl;
    // }
}

Measured memory_bytes: 3348
fn main() {
    let s = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    };

    let (n, m) = {
        let mut ws = s.split_whitespace();
        let n: usize = ws.next().unwrap().parse().unwrap();
        let m: usize = ws.next().unwrap().parse().unwrap();
        (n, m)
    };

    let mut aks: Vec<Vec<usize>> = Vec::new();

    for _i in 0..n {
        let mut ss = String::new();
        std::io::stdin().read_line(&mut ss).unwrap();
        let ss = ss.trim_right().to_owned();
        let mut kak: Vec<usize> = ss.split_whitespace().map(|x| x.parse().unwrap()).collect();
        let ak: Vec<usize> = kak.drain(1..).collect();
        aks.push(ak);
    }
    let mut answer = 0;
    for i in 1..m+1 {
        if aks.iter().all(|ref x| x.iter().any(|&y| y == i))  {
            answer += 1;
        }
    }
    println!("{:?}", answer);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)) cout<<"Yes"<<'\n';
  else cout<<"No"<<'\n';
  return 0;
}


Measured memory_bytes: 256
N = int(input())
SP = [[i for i in input().split()]+[j] for j in range(N)]
for n in range(N):
    SP[n][1] = int(SP[n][1])
SP.sort(key=lambda x:x[1],reverse=True)
SP.sort(key=lambda x:x[0])


        
for n in range(N):
    print(SP[n][2]+1)

Measured memory_bytes: 3060
import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
	
	
	public static void main(String args[])throws Exception{
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] c = new int[M];
		for(int i=0;i<M;i++){
			c[i] = sc.nextInt();
		}
		int[] dp = new int[N+1];
		Arrays.fill(dp, 100000);
		dp[0] = 0;
		for(int i=1;i<=N;i++){
			for(int j=0;j<M;j++){
				if(i-c[j]>=0){
					dp[i] = Math.min(dp[i], dp[i-c[j]]+1);
				}
			}
		}
		System.out.println(dp[N]);
		
		
	}
	
	
}



Measured memory_bytes: 26956
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner scanner=new Scanner(System.in);
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<3;i++){
            stringBuilder.append(scanner.next().charAt(i));
        }
        System.out.println(stringBuilder);
    }
}


Measured memory_bytes: 21716
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define N 1000000

using namespace std;

vector< vector<int> > Init(int& n){
  vector< vector<int> > data(n, vector<int>(n, N));
  for(int i=0; i<data.size(); ++i) data[i][i] = 0;
  return data;
}

void WarshallFloyd(vector< vector<int> >& data){
  for(int k=0; k<data.size(); ++k){
    for(int i=0; i<data.size(); ++i){
      for(int j=0; j<data.size(); ++j){
        data[i][j] = min(data[i][j], data[i][k] + data[k][j]);
      }
    }
  }
}

int GetMinimumCost(const vector< vector<int> >& data1,
		   vector< set<int> >& data2, int s, int g){
  int min_ = N;
  for(int i=0; i<data2.size(); ++i){
    for(set<int>::iterator j=data2[i].begin(); j!=data2[i].end(); ++j){
      for(set<int>::iterator k=data2[*j].begin(); k!=data2[*j].end(); ++k){
	min_ = min(min_, data1[s][i]+data1[*k][g]);
      }
    }
  }
  return min_;
}

int main(){
  int n, m;
  int a, b, c;

  while(1){
    cin >> n >> m;
    if(n == 0 && m == 0) break;

    vector< vector<int> > data1 = Init(n);
    vector< set<int> > data2(n, set<int>());

    for(int i=0; i<m; ++i){
      cin >> a >> b >> c;
      --a;
      --b;
      data1[a][b] = c;
      data1[b][a] = c;
      data2[a].insert(b);
      data2[b].insert(a);
    }

    WarshallFloyd(data1);
    cout << GetMinimumCost(data1, data2, 0, n-1) << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
import sys
def solve():
    N = int(input())
    points = []
    for i in range(N):
        arr = list(map(int, input().split()))
        points.append(arr)
    dp = [[0 for i in range(3)] for j in range(N)]
    dp[0] = points[0]
    for i in range(1, N):
        for j in range(3):
            prev_max = -sys.maxsize
            if j == 0:
                prev_max = max(prev_max, dp[i-1][1], dp[i-1][2])
            elif j == 1:
                prev_max = max(prev_max, dp[i-1][0], dp[i-1][2])
            else:
                prev_max = max(prev_max, dp[i-1][1], dp[i-1][0])
            dp[i][j] = points[i][j] + prev_max
    print(max(dp[N-1]))
solve()

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

const double EPS = 1e-6;
const double INF = 1e12;
const double PI = acos(-1);

using Point = complex<double>;
using Polygon = vector<Point>;

inline int sgn(const double &a) { return (a < -EPS ? -1 : (a > EPS ? 1 : 0)); }

inline bool eq(const Point &a, const Point &b) { return abs(a - b) < EPS; }

namespace std {
inline bool operator<(const Point &a, const Point &b) {
    if (sgn(a.real() - b.real()))
        return sgn(a.real() - b.real()) < 0;
    return sgn(a.imag() - b.imag()) < 0;
}
} // namespace std

double dot(const Point &a, const Point &b) { return real(conj(a) * b); }

double det(const Point &a, const Point &b) { return imag(conj(a) * b); }

struct Line {
    Point p1, p2;

    Line(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {}

    bool operator<(const Line &rhs) const {
        if (eq(p2, rhs.p2))
            return p1 < rhs.p1;
        return p2 < rhs.p2;
    }
    bool operator==(const Line &rhs) const {
        return (eq(p1, rhs.p1) && eq(p2, rhs.p2)) ||
               (eq(p1, rhs.p2) && eq(p2, rhs.p1));
    }
};

inline Point curr(const Polygon &p, const int &i) { return p[i % p.size()]; }

inline Point next(const Polygon &p, const int &i) {
    return p[(i + 1) % p.size()];
}

inline Point prev(const Polygon &p, const int &i) {
    return p[(i + p.size() - 1) % p.size()];
}


enum CCW {
    ONLINE_FRONT = -2,
    CLOCKWISE,
    ON_SEGMENT,
    COUNTER_CLOCKWISE,
    ONLINE_BACK
};

int ccw(Point p0, Point p1, Point p2) {
    Point a = p1 - p0;
    Point b = p2 - p0;
    if (sgn(det(a, b)) == 1)
        return COUNTER_CLOCKWISE;
    if (sgn(det(a, b)) == -1)
        return CLOCKWISE;
    if (sgn(dot(a, b)) == -1)
        return ONLINE_BACK;
    if (sgn(norm(b) - norm(a)) == 1)
        return ONLINE_FRONT;
    return ON_SEGMENT;
}

Point intersection(Line a, Line b) {
    Point v1 = a.p2 - a.p1, v2 = b.p2 - b.p1;
    return a.p1 + v1 * det(v2, b.p1 - a.p1) / det(v2, v1);
}

Polygon convex_cut(const Polygon &pg, const Line &line){
    const int n = pg.size();
    Polygon res;
    for(int i=0;i<n;i++){
        Point p = curr(pg, i), q = next(pg, i);
        if(ccw(line.p1, line.p2, p) != CLOCKWISE)res.push_back(p);
        int is = ccw(line.p1, line.p2, p) * ccw(line.p1, line.p2, q);
        if(is < 0 && is > ONLINE_BACK * ONLINE_FRONT)
            res.push_back(intersection(Line(p, q), line));
    }
    return res;
}

double compute_area(Polygon &poly) {
    double res = 0;
    for (int i = 0; i < poly.size(); i++) {
        res += det(poly[i], poly[(i + 1) % poly.size()]);
    }
    return abs(res) / 2.0;
}

int main(){
    int n;
    cin >> n;
    Polygon pg;
    for(int i=0;i<n;++i){
        double x, y;
        cin >> x >> y;
        pg.push_back(Point(x, y));
    }
    int q;
    cin >> q;
    for(int i=0;i<q;++i){
        double p1x, p1y, p2x, p2y;
        cin >> p1x >> p1y >> p2x >> p2y;
        Line line(Point(p1x, p1y), Point(p2x, p2y));
        Polygon poly = convex_cut(pg, line);
        printf("%.10f\n", compute_area(poly));
    }

    return 0;
}



Measured memory_bytes: 3260
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    char c;
    cin >> c;
    char ans;
    if (c == 'A')
    {
        ans = 'T';
    }else if (c == 'C')
    {
        ans = 'G';
    }else if (c == 'G')
    {
        ans = 'C';
    }else if (c == 'T')
    {
        ans = 'A';
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
// =====================================================================================
// 
//       Filename:  A.cpp
//        Created:  2017년 06월 10일 20시 55분 16초
//       Compiler:  g++ -O2 -std=c++14
//         Author:  baactree ,  bsj0206@naver.com
//        Company:  Chonnam National University
// 
// =====================================================================================

#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int main(){
	scanf("%d%d%d", &a, &b, &c);
	int out=a*100+b*10+c;
	printf("%s\n", (out%4==0)?"YES":"NO");
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
namespace ZDY{
    #pragma GCC optimize(3)
    #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
    #pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
    #define il __inline__ __attribute__ ((always_inline))
    #define rg register
    #define ll long long
    #define db double
    #define sht short
    #define MB template <class T>
    #define Fur(i,x,y) for(rg int i=x;i<=y;i++)
    #define Fdr(i,x,y) for(rg int i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdout)
    #define l2(n) (int(log2(n)))
    #define inf 2000000000
    #define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define fcin ios::sync_with_stdio(false)
    MB T ABS(T x){return x>0?x:-x;}
    MB T MAX(T x,T y){return x>=y?x:y;}
    MB T MIN(T x,T y){return x<=y?x:y;}
    MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
    void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 100011
#define int ll
int n,m;
struct node{
    int a,b;
}t[N];
bool cmp(node x,node y){
    if(x.a!=y.a)return x.a<y.a;
    return x.b>y.b;
}
signed main(){
    in>>n>>m;
    Fur(i,1,n)in>>t[i].a>>t[i].b;
    sort(t+1,t+n+1,cmp);
    int ans=0,d=1;
    while(m>0)
        if(m>=t[d].b)ans+=t[d].a*t[d].b,m-=t[d++].b;
        else ans+=m*t[d].a,m=0;
    out<<ans<<ln;
}

Measured memory_bytes: 2816
#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional> //sort(A,A.end(),greater<int>());???????????????
#include <queue>
#include <stack>
#include <vector>

#define INF 10 << 10

struct ank {
	int cnt = 0;
	int number;
};

int main() {
	int n, m;

	while (cin >> n >> m && n != 0 && m != 0) {
		ank AN[124];
		for (int i = 0; i < n; ++i) {
			for (int i2 = 1; i2 <= m; ++i2) {
				AN[i2].number = i2;
				int num;
				cin >> num;
				if (num == 1) {
					++AN[i2].cnt;
				}
			}
		}
		
		//??????????????????
		bool flg = true;
		for (int i = 1; flg; ++i) {
			flg = false;
			for (int j = m; j >= i + 1; --j) {
				if (AN[j].cnt > AN[j - 1].cnt) {
					swap(AN[j], AN[j - 1]);
					flg = true;
				}
			}
		}

		for (int i = 1; i <= m; ++i) {
			cout << AN[i].number;
			if (i != m) {
				cout << ' ';
			}
			else {
				cout << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3076
#include <stdio.h>

int main(){
	int a, b, c, N, i;

	scanf("%d",&N);
	for(i = 0; i < N; i++){
		scanf("%d %d %d",&a, &b, &c);
		if(chk(a, b, c)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

int chk(int a, int b, int c){
	int x;

	if(a >= b){
		x = a;
		a = b;
		b = x;
	}

	if(b >= c){
		x = b;
		b = c;
		c = x;
	}

	if(a >= b){
		x = a;
		a = b;
		b = x;
	}

	if(c*c == a*a + b*b) return 1;
	else return 0;
}

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

class dice{
public:
    int sur1, sur2, sur3, sur4, sur5, sur6, temp;

    dice(int surf1,int surf2,int surf3,int surf4,int surf5,int surf6){
        temp = 0;
        sur1 = surf1;
        sur2 = surf2;
        sur3 = surf3;
        sur4 = surf4;
        sur5 = surf5;
        sur6 = surf6;
    }

    void move(char dire){
        if(dire == 'N'){
            temp = sur2;
            sur2 = sur6;
            sur6 = sur5;
            sur5 = sur1;
            sur1 = temp;//??????????????????
        }
        else if(dire == 'E'){
            temp = sur3;
            sur3 = sur1;
            sur1 = sur4;
            sur4 = sur6;
            sur6 = temp;
        }
        else if(dire == 'W'){
            temp = sur4;
            sur4 = sur1;
            sur1 = sur3;
            sur3 = sur6;
            sur6 = temp;
        }
        else if(dire == 'S'){
            temp = sur6;
            sur6 = sur2;
            sur2 = sur1;
            sur1 = sur5;
            sur5 = temp;
        }
    }
        void print(){
            cout << sur1 << endl;
        }


};

int main(){
    int a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;
    dice dice1(a,b,c,d,e,f);
    string direc;
    cin >> direc;

    for(int i = 0; i < direc.size(); i++){
        //cout << direc[i];
        dice1.move(direc[i]);
        //dice1.print();
    }

    dice1.print();

    return 0;
}

Measured memory_bytes: 3164
#!/usr/bin python3
# -*- coding: utf-8 -*-

import itertools
L = [''.join(i) for i in itertools.product('0123', repeat=3)]
l = len(L)

mod = 10**9+7

AGC = '021'
ACG = '012'
GAC = '201'
nc3 = set([AGC, ACG, GAC])

AGGC = '0221'
AGTC = '0231'
ATGC = '0321'
nc4 = set([AGGC, AGTC, ATGC])

n = int(input())
dp = [[0]*l for _ in range(n+1)]
for i in L:
    if i in nc3: continue
    dp[3][int(i, 4)] = 1

for i in range(3, n):
    for jl in L:
        for k in "0123":
            nxt = jl[1:] + k
            if nxt in nc3: continue
            if jl+k in nc4: continue
            dp[i+1][int(nxt, 4)] += dp[i][int(jl, 4)]
print(sum(dp[n])%mod)


Measured memory_bytes: 9168
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
    

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

a = [0] * m
b = [0] * m

for i in range(m):
    a[i], b[i] = map(int,input().split())
    a[i]-= 1
    b[i]-= 1

res = 0
for i in range(m):
    UF = UnionFind(n)
    for j in range(m):
        if j != i:
            UF.union(a[j],b[j])
    if UF.group_count() ==2:
        res += 1

print(res)

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

const int N = 1e5 + 5;


long long xor_sum(long long a) {
    //xor sum: 0^1^2^...^a
    if (a % 4 == 0) return a;
    if (a % 4 == 1) return 1;
    if (a % 4 == 2) return a + 1;
    return 0;
}


int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll a, b;
    cin>>a>>b;

    cout<<(xor_sum(b)^xor_sum(a-1))<<endl;
    
    return 0;
}


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

using namespace std;
#define rep(i,n) for (int i =0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;

const int INF = 1001001001;

int main() {
    int  K;
    string S;
    cin >>K>>S; 
    if(S.length()>K){
        rep(i,K)cout <<S[i];
        cout <<"...";
    }
    else cout <<S;
    return 0;
}

Measured memory_bytes: 3628
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

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

#define ALL(v) (v).begin(),(v).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000007;
const int INF = 1e9;

const double EPS = 1e-9;
const double PI = acos(-1.0);

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

int A, B, C;

int main() {
    cin >> A >> B >> C;
    if (A == B && B != C || B == C && C != A || C == A && A != B) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
use std::io::stdin;
use std::cmp::max;

fn main() {
    let (n, k) = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        let mut ws = s.trim_right().split_whitespace();
        let n: i64 = ws.next().unwrap().parse().unwrap();
        let k: i64 = ws.next().unwrap().parse().unwrap();
        (n, k)
    };

    let mut a = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        let mut ws = s.trim_right().split_whitespace();
        let mut a: Vec<i64> = vec![];
        while let Some(_a) = ws.next() {
            a.push(_a.parse().unwrap())
        }
        a
    };

    let mut f = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        let mut ws = s.trim_right().split_whitespace();
        let mut f: Vec<i64> = vec![];
        while let Some(_f) = ws.next() {
            f.push(_f.parse().unwrap())
        }
        f
    };

    a.sort();
    f.sort();
    f.reverse();

    let mut r: i64 = (1e12 as i64);
    let mut l: i64 = -1;

    while (r - l > 1) {
        let mut mid = (((r+l)/2) as i64);
        let ok = {
            let mut sum = 0;
            for i in 0..(n as usize) {
                sum += max(a[i] - (mid as i64)/f[i], 0);
            }
            sum <= k
        };
        if ok {r = mid } else { l = mid }
    }

    println!("{}", r);
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

struct pos{
  int x;
  int y;
  int d;
};

int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<int>> field(h,vector<int>(w));
  int black=0;
  char c;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c;
      if(c=='#'){
        field[i][j]=1;
        black++;
      }else field[i][j]=0;
    }
  }
  int houkou[5]={0,1,0,-1,0};
  int nx,ny;
  queue<struct pos> bfs;
  bfs.push({0,0,0});
  field[0][0]=1;
  struct pos now;
  while(!bfs.empty()){
    now=bfs.front();
    bfs.pop();
    for(int i=0;i<4;i++){
      nx=now.x+houkou[i];
      ny=now.y+houkou[i+1];
      if(0<=nx&&nx<w&&0<=ny&&ny<h){
        if(!field[ny][nx]){
          bfs.push({nx,ny,now.d+1});
          field[ny][nx]=1;
        }
        if(nx==w-1&&ny==h-1){
          cout << h*w-black-now.d-2 << endl;
          return 0;
        }
      }
    }
  }
  cout << -1 << endl;
  return 0;
}


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

int main() {

	int n; cin >> n;
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	vector<int> c(n);
	for (int i = 0; i < n; i++) {
		c[i] = i;
	}
	vector<double> t;
	do {
		double tmp = 0;
		for (int i = 1; i < n; i++) {
			tmp += (double)sqrt((x[c[i]] - x[c[i - 1]]) * (x[c[i]] - x[c[i - 1]]) + (y[c[i]] - y[c[i - 1]]) * (y[c[i]] - y[c[i - 1]]));
		}
		t.push_back(tmp);
	} while (next_permutation(c.begin(), c.end()));
	double ans = 0;
	for (int i = 0; i < t.size(); i++) {
		ans += t[i];
	}
	cout << fixed << setprecision(11) << ans / t.size() << endl;
}

Measured memory_bytes: 3952
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        String S = sc.next();
        char[] c = S.toCharArray();
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int i=N;
        int flag = 0;
        loop:while (i>=0) {
            for (int j=M;j>=1;j--) {
                if (i-j<0) continue;
                if (c[i-j]=='0') {
                    i-=j;
                    ans.add(j);
                    break;
                }
                if (j==1) {
                    flag = 1;
                    break loop;
                }
            }
            if (i==0) break;
        }
        if (flag==1) {
            System.out.println(-1);
        } else {
            for (int j=ans.size()-1;j>=0;j--) {
                System.out.println(ans.get(j));
            }
        }
    }
}

Measured memory_bytes: 38100
#include <bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		UL N; cin >> N;
		vector<pair<LL, LL>> R(N);
		rep(i, N) cin >> R[i].first >> R[i].second;
		R.push_back({ 0, 0 });
		LL l = -100001, r = 100001;
		while (l + 1 < r) {
			LL m = (l + r) / 2;
			UL a = 0, b = 0;
			rep(i, N + 1) {
				if (m < R[i].first) b++;
				if (R[i].second < m) a++;
			}
			if (a <= b) l = m;
			else r = m;
		}
		LL ans = 0;
		for (LL O : {l, r}) {
			LL ansbuf = 0;
			vector<UL> Ls, Rs;
			rep(i, N) {
				if (O <= R[i].first) Ls.push_back(R[i].first - O);
				if (R[i].second <= O) Rs.push_back(O - R[i].second);
			}
			sort(Ls.begin(), Ls.end());
			sort(Rs.begin(), Rs.end());
			if (O <= 0) Ls.push_back(-O);
			if (0 <= O) Rs.push_back(O);
			reverse(Ls.begin(), Ls.end());
			reverse(Rs.begin(), Rs.end());
			rep(i, min(Ls.size(), Rs.size())) {
				ansbuf += Ls[i] + Rs[i];
			}
			ans = max(ansbuf, ans);
		}
		ans *= 2;
		cout << ans << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

Measured memory_bytes: 4864
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int n = s.length;
        int c = 0;
        for (int i = 0 ; i < n/2 ; i++) {
            if (s[i] != s[n-1-i]) c++;
        }

        System.out.println(c);
    }

}

Measured memory_bytes: 25300
while True:
    n, r = map(int, input().split())
    if n == r == 0:
        break
    cs = list(range(n))
    for i in range(r):
        p, c = map(int, input().split())
        of = n - c - p + 1
        cs = cs[:of] + cs[of + c:] + cs[of:of+c]

    print(cs[-1] + 1)
    


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

void solve(string s) {
	int i, joi = 0, ioi = 0;
	for (i = 0; i < s.size() - 2; i++) {
		if (s[i] == 'J'&&s[i + 1] == 'O'&&s[i + 2] == 'I') joi++;
		if (s[i] == 'I'&&s[i + 1] == 'O'&&s[i + 2] == 'I') ioi++;
	}
	cout << joi << endl;
	cout << ioi << endl;
}

int main() {
	string s;
	while (cin >> s) {
		solve(s);
	}
	return 0;
}

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

int main() {
  int s, t, u, v;
  cin >> s;
  t = s / 100;
  u = ( s - 100 * t) / 10;
  v = ( s - 100 * t - 10 * u );
  cout << (t + u + v) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

int gcd(int m, int n) {
  if (n > m) {
    std::swap(m, n);
  }
  if (n <= 0) {
    return m;
  }
  return gcd(n, m % n);
}

int solve(int n, std::vector<int> as) {
  std::vector<int> lefts(n);
  lefts[0] = as[0];
  for (int i = 1; i < n; ++i) {
    lefts[i] = gcd(as[i], lefts[i - 1]);
  }
  std::vector<int> rights(n);
  rights[n - 1] = as[n - 1];
  for (int i = n - 2; i >= 0; --i) {
    rights[i] = gcd(as[i], rights[i + 1]);
  }
  assert(lefts[n - 1] == rights[0]);
  int ret = lefts[n - 1];
  ret = std::max(lefts[n - 2], ret);
  ret = std::max(rights[1], ret);
  for (int i = 1; i < n - 1; ++i) {
    int const candidate = gcd(lefts[i - 1], rights[i + 1]);
    ret = std::max(candidate, ret);
  }
  return ret;
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t n;
  std::cin >> n;
  std::vector<int> as(n);
  for (int i = 0; i < n; i++) {
    std::cin >> as[i];
  }
  auto const res = solve(n, std::move(as));
  std::cout << res << std::endl;
  return 0;
}


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

int main(){
  long long N, L, T;
  cin >> N >> L >> T;
  //T %= L;
  vector<long long> X;
  int c = 0;
  for(int i = 0; i < N; ++i){
    long long x, w, x_;
    cin >> x >> w;
    if(w == 1) x_ = x+T;
    else x_ = x-T;
    c += x_/L;
    x_ %= L;
    if(x_ < 0) --c, x_ += L;
    X.push_back((L+x_%L)%L);
  }
  //cerr << c << endl;
  sort(X.begin(), X.end());
  for(int i = 0; i < N; ++i){
    cout << X[(i+N+c%N)%N] << endl;
  }
}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<class F>auto recursive(F f){return[f](auto...a){return f(f,a...);};}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int p;fixprec(int p):p(p){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.p);}
int main() {
    int N;
    cin >> N;
    vector<i64> A(N);
    map<i64, i64> B;
    i64 ans = 0;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        ans += B[i - A[i]];
        B[A[i] + i]++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 27484
/********************************************//**
 ****** Handle: techno_phyle    *****************
 ***********************************************/

#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
#define mod 1000000007
#define N 100010
#define M 200010
#define db(a) cout << a << endl
#define db2(a,b) cout << a << " " << b << endl
#define dbp(a) cout << a.first << " " << a.second << endl
#define adb(a) for(auto it:a) cout << it << " "; cout << endl
#define adbp(a) for(auto it:a) cout << it.first << " " << it.second << endl
#define pb push_back
#define mp make_pair
#define endline "\n"
#define in(x) scanf("%d",&x);
const ll INF = 1e18L + 5;
const int inf = 1e9 + 5;
typedef pair<double, long> key;
struct comp {
	bool operator()(pair<int, int> p1, pair<int, int> p2) {
		if (p1.first < p2.first) return false;
		if (p2.first < p1.first) return true;
		return p1.second < p2.second;
	};
};
//greater<pair<int,int> , greater<int>>


int main() {
	fastIO;
	int test = 1;
	//cin >> test;
	while (test--) {
		string s;
		cin >> s;
		int cnt = 0 , ans = 0;
		for (int i = 0; i < 3; i++) {
			if (s[i] == 'R') {
				cnt++;
				ans = max(ans , cnt);
			}
			else cnt = 0;
		}
		cout << ans << endl;
	}

	return 0;

}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

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

	int n; cin >> n;

	vector<int> vs(n + 1);
	FOR_LT(i, 0, n) {
		int v; cin >> v;
		vs[v]++;
	}

	sort(vs.begin(), vs.end(), greater<int>());

	vector<int> steps(n + 1);

	steps[vs[0]] = 1;
	FOR_LT(i, 1, n) {
		int v = vs[i];
		FOR_DW(j, vs[i - 1] - 1, v + 1) {
			steps[j] = i;
		}
		steps[v] = i + 1;
	}

	vector<int> ans(n + 1);
	FOR_DW(i, n - 1, 0) {
		if (vs[i + 1] != 0) {
			int v = vs[i + 1];
			int c = v;
			while (c != 0) {
				while (steps[v + 1] > i) v++;

				vs[steps[v + 1]]++;
				steps[v + 1]++;
				c--;
			}
		}

		ans[i] = vs[i];
	}

	FOR_LT(i, 0, n) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 4352
from scipy.sparse import *;N=int(input());Z=[[i]+list(map(int,input().split())) for i in range(N)];P=set()
for j in [1,2]:Z.sort(key=lambda a:a[j]);P|={(min(abs(Z[i][1]-Z[i-1][1]),abs(Z[i][2]-Z[i-1][2])),Z[i-1][0],Z[i][0]) for i in range(1,N)}
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Measured memory_bytes: 81592
#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int q;
    cin >> q;
    while( q-- ){
        int count = 0;
        int n;
        cin >> n;
        while( n >= 10 ){
            int d = 0;
            int max = 0;
            while( d++ < 6){
                int a, b;
                a = n / pow( 10, d );
                b = n % (int)pow( 10, d );
                if( max < a * b ) max = a * b;
            }
            count++;
            n = max;
        }
        cout << count << endl;
    }
}

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

int main() {
  int X,  y = 0,happy = 0;
  cin >> X;
  
  y = (X / 500) ;
  happy += y * 1000;
  
  y = (X % 500) ;
  happy += (y / 5) * 5;
  
  cout << happy << endl;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
	public static void main (String[] args){
		Scanner sc =  new Scanner(System.in);
		long H = sc.nextLong();
		long W = sc.nextLong();
		long r = H*W;
		r = r/2;
		if(H%2!=0 && W%2!=0) {
			r++;
		}
		if(H == 1 || W == 1) {
			r = 1;
		}
		System.out.println(r);
	}	
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	int arr[a];
	for(int i=0; i<a; i++)
		cin >> arr[i];
	int dp[a] = {0};
	for(int i=1; i<a; i++)
	{
		dp[i] = dp[i-1] + abs(arr[i] - arr[i-1]);
		for(int j=i; j>=0 && j >= i - b; j--)
		{
			dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]));
		}
	}
	printf("%d\n",dp[a - 1]);
	return 0;
} 

Measured memory_bytes: 1024
#include<stdio.h>

int main(){
  int n, i, max, min;
  scanf("%d", &n);
  int A[n];
  for(i = 0 ; i < n ; i++){
    scanf("%d", &A[i]);
  }
  max = A[1] - A[0];
  min = A[0];
  for(i = 1 ; i < n ; i++){
    if(min > A[i - 1]) min = A[i - 1];
    if(max < A[i] - min) max = A[i] - min;
  }
  printf("%d\n", max);
}



Measured memory_bytes: 2564
#include<iostream>
using namespace std;
int n,s,x,y,z;
main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        if(s%4==0)x++;
        else if(s%2==0)y++;
        else z++;
    }
    if(x>=z)cout<<"Yes"<<"\n";
    else if(z-x==1 and y==0)cout<<"Yes"<<"\n";
    else cout<<"No"<<"\n";     
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n,k;cin>>n>>k;
    vll x(n),y(n);
    rep(i,n)cin>>x[i]>>y[i];
    ll area=5*INF;int res;ll a,b,c,d;
    rep(i,n)rep(j,n)rep(l,n)rep(m,n){//left x,right x,under y,up y
       a=x[i];b=x[j];c=y[l];d=y[m];
       res=0;
       rep(h,n){
           if(a<=x[h]&&x[h]<=b&&c<=y[h]&&y[h]<=d)res++;
       }
       if(res>=k)area=min(area,(b-a)*(d-c));
   }
   cout<<area<<endl;
}

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

#define    int               long long int
 #define    bp(x)         __builtin_popcount(x)
#define  ld         long double
 #define  f(i,j,n)            for(int i = j; i <= n; i++)
#define  r(i,n,j)       for(int i = n; i >= j; i--)
 #define  all(container)       container.begin() , container.end()
#define  sz(container)   (int)container.size()
 #define  ff             first
#define  ss             second
 #define  pii      pair <int , int>
#define  sp(x)       setprecision(x)
#define  mod  1000000007
#define  endl  "\n"
 #define  pb    push_back
#define  mp    make_pair
 #define  T     int ttt; cin >> ttt; while(ttt--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int power(int x, int y, int p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)  
    {     
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res; 
}

int32_t main()
{
    fast
    int n;   cin>>n;
    f(i,1,n)    cout<<"ACL";
}

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

int main() {
  vector<int> v(3);
  for (int i = 0; i < 3; i++) cin >> v[i];
  int K;
  cin >> K;

  sort(v.begin(), v.end(), greater<int>());
  for (int i = 0; i < K; i++) v[0] *= 2;
  cout << accumulate(v.begin(), v.end(), 0) << endl;
}


Measured memory_bytes: 256