akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

class Coordinate{
    private int x, y;
    public void set(int x_cor, int y_cor){
        x = x_cor;
        y = y_cor;
    }

    public boolean exist(int x_cor, int y_cor){
        if (x == x_cor && y == y_cor){
            return true;
        }
        return false;
    }
}

class Island {
    private HashSet<Coordinate> coordinates = new HashSet<Coordinate>();

    public void new_coords(int x_cor, int y_cor) {
        Coordinate f_coordinate = new Coordinate();
        f_coordinate.set(x_cor, y_cor);
        coordinates.add(f_coordinate);
    }

    public HashSet<Coordinate> getCoordinates(){
        return coordinates;
    }

    public void clear(){
        coordinates.clear();
    }

    public boolean adjacent(int x_cor, int y_cor) {
        Iterator<Coordinate> iterator = coordinates.iterator();
        while (iterator.hasNext()) {
            Coordinate tmp_coords = iterator.next();
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (tmp_coords.exist(x_cor + i, y_cor + j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public void merge(Island target){
        coordinates.addAll(target.getCoordinates());
        target.clear();
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            HashSet<Island> islands = new HashSet<Island>();
            int w = sc.nextInt(), h = sc.nextInt();
            if (w == 0 && h == 0) break;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (sc.nextInt() == 1) {
                        Island tmp_island = new Island();
                        tmp_island.new_coords(i, j);
                        HashSet<Island> removing = new HashSet<Island>();
                        Iterator<Island> iterator = islands.iterator();
                        while (iterator.hasNext()) {
                            Island iter_island = iterator.next();
                            if (iter_island.adjacent(i, j)) {
                                tmp_island.merge(iter_island);
                                removing.add(iter_island);
                            }
                        }
                        islands.removeAll(removing);
                        islands.add(tmp_island);
                    }
                }
            }
            System.out.println(islands.size());
        }
    }
}

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

int main(void)
{
    int N, M, sum=0;
    cin >> N >> M;
    vector<int> a(N);
    for (int i = 0; i< N; i++){
        cin >> a.at(i);
        sum += a.at(i);
    }
    int count=0;
    for (int i = 0; i<N; i++){
        if(sum <= a.at(i)*(4*M)){
            count++;
        }
    }
    if (count>=M && count >= 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long A = sc.nextLong();
        long B = sc.nextLong();


        long base = N / (A + B);
        long mod = N % (A + B);
        if (mod >= A) mod = A;
       
        System.out.println(base * A + mod);

        return;
    }

}

Measured memory_bytes: 22100
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
 
N, M = MAP()
 
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]
 
if A == B:
	print("Yes")
	exit()

for i in range(N-M):
	for j in range(N-M):
		for k in range(M):
			if A[i+k][j:j+M] != B[k]:
				break
		else:
			print("Yes")
			exit()
else:
	print("No")

Measured memory_bytes: 5204
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int n = input[0], m = input[1];

            List<List<int>> table = new List<List<int>>();
            int[] group = new int[n];
            for (int i = 0; i < n; i++)
            {
                table.Add(new List<int>());
                group[i] = -1;
            }

            for (int i = 0; i < m; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

                table[input[0]].Add(input[1]);
                table[input[1]].Add(input[0]);
            }

            for (int i = 0, g = 0; i < n; i++)
            {
                if (group[i] == -1) DFS(table, group, i, g++);
            }

            StringBuilder sb = new StringBuilder();
            int q = int.Parse(Console.ReadLine());

            for (int i = 0; i < q; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

                sb.AppendLine(group[input[0]] == group[input[1]] ? "yes" : "no");
            }
            Console.Write(sb);
        }

        static void DFS(List<List<int>> table, int[] group, int u, int g)
        {
            Stack<int> stk = new Stack<int>();
            group[u] = g;
            stk.Push(u);

            while (stk.Count > 0)
            {
                int temp = stk.Pop();

                foreach (var friend in table[temp])
                {
                    if (group[friend] == -1)
                    {
                        group[friend] = g;
                        stk.Push(friend);
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 23788
n=int(input())
A=[int(input().replace(' ',''),2)for _ in[0]*n]
p=[0]*2**n
p[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]&~I
 for j in range(n):
  if a&1<<j:p[I|1<<j]+=p[I]
print(p[-1]%(10**9+7))

Measured memory_bytes: 113372
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define SZ size()
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define REP(i, n) FOR((i), 0, (n))
#define GET(a) cin >> (a)
#define GET2(a, b) cin >> (a) >> (b)
#define GET3(a, b, c) cin >> (a) >> (b) >> (c)
#define SHOW(v) cout << (v) << endl
#define SHOW2(a, b) cout << (a) << " " << (b) << endl
#define SHOW3(a, b, c) cout << (a) << " " << (b) << " " << (c) << endl
#define MOD 1000000007
template<class T> void GETV(T &v) { REP(i, v.size()) { GET(v[i]); } }
template<class T> void SHOWV(T &v) { REP(i, v.size()) { SHOW(v[i]); } }

typedef long long ll;

int main() {
	int n;
	cin >> n;
	
	string s;
	cin >> s;
	
	int white = 0;
	int black = n;
	for(int i = 0; i < n; i++) {
		if(s[i] == '.') {
			white++;
		}
		else {
			black++;
		}
	}
	
	int left = 0;
	int ans = white < black ? white : black;
	int add = 0;
	for(int i = 0; i < n; i++) {
		if(s[i] == '.') {
			left++;
		}
		else {
			add++;
		}
		
		if(ans > add + white - left) {
			ans = add + white - left;
		}
	}
	
	cout << ans << endl;
	
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
using namespace std;

void solve(){
  vector<vector<char> > v(3, vector<char>(3));
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++) cin >> v[i][j];
  }
  cout << v[0][0] << v[1][1] << v[2][2] << endl;
  return;
}

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


Measured memory_bytes: 256
import numpy as np
n,m,c=map(int,input().split())
b_s = list(map(int,input().split()))
a_s = [list(map(int,input().split())) for _ in range(n)]
b_num = np.array(b_s)
count = 0
for a in a_s:
    a_num = np.array(a)
    res = np.dot(a_num,b_num)
    if res + c > 0:
        count += 1
print(count)

Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  ll ans=0;
  REP(i,1,n) {
    ans+=(n-1)/i;
  }
  pr(ans);
}

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


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll bitcount(ll x){
  if(x==0) return 0;
  return bitcount(x>>1)+(x&1);
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vector<vpll> v(n);
  rep(i,n){
    ll a; cin>>a;
    rep(j,a){
      ll x,y; cin>>x>>y; x--;
      v[i].emplace_back(x,y);
    }
  }
  
  ll ans=0;
  for(ll bit=0; bit<(1<<n); bit++){
    bool ok=true;
    rep(i,n){
      if(bit>>i&1){
        for(auto e: v[i]){
          ll x=e.first, y=e.second;
          if(bit>>x&1){
            if(y!=1) ok=false;
          }else{
            if(y==1) ok=false;
          }
        }
      }
    }
    if(ok){
      chmax(ans,bitcount(bit));
    }
  }
  cout<<ans<<endl;
  
}

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

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    string S = in<string>();
    char A = S[0];
    bool ok = 1;
    if(S[1] != A)ok = 0;
    if(S[2] != A)ok = 0;
    if(S[1] != S[2])ok = 0;
    cout << (ok ? "No" : "Yes") << "\n";
}

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

int main() {
  int Th, Ta, Ah, Aa;
  cin >> Th >> Ta >> Ah >> Aa;
  
  while(true){
  Ah -= Ta;
  if(Ah <= 0){
    cout << "Yes" << endl;
    break;
  }
  Th -= Aa;
  if(Th <= 0){
    cout << "No" << endl;
    break;
  }
  }
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion
#define MAX 111111



int main(void) {
  string s1, s2;
  cin >> n;
  cin >> s1;
  cin >> s2;

  FOR(i, 0, s1.length()) {
	flag = true;
	FOR(j, 0, s1.length() - i) {
	  if (s2[j] != s1[i + j]) {
		flag = false;
		break;
	  }
	}
	if (flag) {
	  ans = s1.length() + i;
	  break;
	}
  }
  if (ans == 0) ans = s1.length() * 2;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MN 200000
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,a[MN+5];
bool Check(int x)
{
    int L,R=n,OO=n;
    for(int i=1,j=n;i<<1<=n;++i)
    {
        while(j&&a[i]+a[j]>x) --j;
        R=min(R,j+i-1);
        if(R<i<<1) {OO=(i-1)<<1;break;}
    }
    if(OO==n) return true;
    L=1;R=n;
    for(int i=n,j=1,k=1;i>n>>1;--i)
    {
        while(j<=n&&a[i]+a[j]<m) ++j;
        while(k<=n&&a[i]+a[k]<=m+x) ++k;
        //cout<<"Check"<<x<<" "<<OO<<" "<<i<<" "<<j<<" "<<k<<endl;
        L=max(L,i+j-n);R=min(R,k+i-n-1);
        int pos=i-(n-i+1);
        if(pos>=L&&pos<=R&&pos-1<=OO) return true;
    }
    return false;
}
int main()
{
    n=read()*2;m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+n+1);
    int l=0,r=m-2,mid,res=m-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(Check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<res;
    return 0;
}

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

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

    while (in.hasNext()) {
      int N = in.nextInt();
      int M = in.nextInt();
      Shop[] shop = new Shop[N];

      for (int i = 0; i < shop.length; ++i) {
        shop[i] = new Shop(in.nextInt(), in.nextInt());
      }
      
      Arrays.sort(shop);

      long cost = 0;
      for (int i = 0; M > 0; ++i) {
        cost += (long)shop[i].price * Math.min(M, shop[i].numOfDrink);
        M -= shop[i].numOfDrink;
      }

      System.out.println(cost);
    }
  }

  private static class Shop implements Comparable<Shop>{
    int price;
    int numOfDrink;
    
    Shop (int price, int numOfDrink) {
      this.price = price;
      this.numOfDrink = numOfDrink;
    }

    @Override
    public int compareTo(Shop s) {
      return this.price - s.price;
    }
  }
}

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

const int MAX_N = (int)(40 + 5);
const int MAX_UNIT = (int)(400 + 5);

struct matter {int a, b, c;};

int n, ma, mb;
matter items[MAX_N];

int dp[MAX_N][MAX_UNIT][MAX_UNIT];

int ans;

int main(void) {
  // Here your code !
  scanf("%d %d %d", &n, &ma, &mb);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d %d", &(items[i].a), &(items[i].b), &(items[i].c));
  }

  for (int i = 0; i <= n; ++i) {
    for (int ua = 0; ua <= MAX_UNIT - 1; ++ua) for (int ub = 0; ub <= MAX_UNIT - 1; ++ub) {
      dp[i][ua][ub] = -1;
    }
  }

  dp[0][0][0] = 0;

  for (int i = 1; i <= n; ++i) {
    for (int ua = 0; ua <= MAX_UNIT - 1; ++ua) for (int ub = 0; ub <= MAX_UNIT - 1; ++ub) {

      dp[i][ua][ub] = dp[i - 1][ua][ub];

      if ((ua - items[i].a) >= 0 && (ub - items[i].b) >= 0 && dp[i - 1][ua - items[i].a][ub - items[i].b] > -1) {
        int cand = dp[i - 1][ua - items[i].a][ub - items[i].b] + items[i].c;

        // cout << i << "_" << ua << "_" << ub << "_" << cand << "_" << dp[i][ua][ub] << endl;
        dp[i][ua][ub] = (dp[i][ua][ub] > -1) ? min(dp[i][ua][ub], cand) : cand;
      }
      else {
        if (ua == items[i].a && ub == items[i].b) {
          if (dp[i][ua][ub] > -1) {
            dp[i][ua][ub] = min(dp[i][ua][ub], items[i].c);
          }
          else dp[i][ua][ub] = items[i].c;
        }
      }

    }
  }

  ans = 114514;
  for (int ua = 1; ua <= MAX_UNIT - 1; ++ua) {
    for (int ub = 1; ub <= MAX_UNIT - 1; ++ub) {
      // printf("%d ", dp[n][ua][ub]);
      if ((ua / ma) == (ub / mb) && (ua % ma) == 0 && (ub % mb) == 0) {
        // cout << dp[n][ua][ub] << endl;
        ans = dp[n][ua][ub] > -1 ? min(ans, dp[n][ua][ub]) : ans;
      }
    }
    // printf("\n");
  }

  ans = ans == 114514 ? -1 : ans;

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 26880
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.14159265359

int main() {
    string n;
    cin >> n;
    ll sum = 0;
    while(!n.empty()){
        char hoge = n.back();
        n.pop_back();
        sum += (int)(hoge - '0');
    }
    if(sum%9==0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3752
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String args[]) throws Exception {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		
		long n = sc.nextLong();
		long k = sc.nextLong();
		long min = n;
		if(k == 1) {
			System.out.println("0");
			return;
		}
		if(n % k == 0) {
			System.out.println("0");
			return;
		}
		if(n > k) {
			long divisor = n / k;
			long rem = n - (divisor * k);
			n = rem;
		}
		min = n;
		while(Math.abs(n - k) <= min) {
			n = Math.abs(n - k);
			min = Math.min(min, n);
		}
		System.out.println(n);
	}

	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}

}


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=(0);i<(n);i++)
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<double> vd;
typedef vector<string> vs;
const int mod = (int)1e9+7;
int main(){
	string s;
	cin>>s;
	int sum=0;
	for(char c:s){
		sum+=c-'0';
	}
	if(sum%9==0) cout<<"Yes";
	else cout<<"No";

	return 0;
}

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

int main() {
  int n;
  cin >> n;
  int a[50], b[50], c[50];

  for(int i=0; i < n; i++){
    cin >> a[i];
    a[i]--;
  }
  for(int i=0; i < n; i++){
    cin >> b[i];
  }
  for(int i=0; i < n-1; i++){
    cin >> c[i];
  }
  int result =0;
  for(int i=0; i<n; i++) {
    result += b[a[i]];
    if(i != 0) if(a[i]-1 == a[i-1]) result += c[a[i-1]];
  }
  cout << result << endl;
}



Measured memory_bytes: 256
n, m, d = map(int, input().split())
fig = [list(input()) for i in range(n)]

hor = []
for i in range(n):
    tmp = 0
    for j in range(m):
        if fig[i][j]==".": tmp += 1
        else:
            hor.append(tmp)
            tmp = 0
    hor.append(tmp)

ver = []
for i in range(m):
    tmp = 0
    for j in range(n):
        if fig[j][i]==".": tmp += 1
        else:
            ver.append(tmp)
            tmp = 0
    ver.append(tmp)

ans = 0
for i in hor:
    if i-d>=0: ans += i-d+1
for i in ver:
    if i-d>=0: ans += i-d+1
print(ans)


Measured memory_bytes: 5640
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

int main()
{
  int n, m, k;
  while(1){
    m = 0;
    k = 0;
    cin >> n;
    if(n == 0){
      break;
    }else{
      int num[n][2];
      pii p[n];
      for(int i = 0; i < n; i++)
	cin >> num[i][0] >> num[i][1];
      for(int i = 0; i < n; i++)
	p[i] = make_pair(num[i][1], num[i][0]);
      sort(p, p + n);
      for(int i = 0; i < n; i++){
	m += p[i].second;
	if(m > p[i].first){
	  cout << "No" << endl;
	  k = i;
	  break;
	}
	if(i == n - 1 && k == 0)
	  k = n - 1;
      }
      if(m <= p[k].first)
	cout << "Yes" << endl;
    }
  }
}

Measured memory_bytes: 1156
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n,k;
vector<int> G[100000];
bool used[100000];
ll ans = 1;
void dfs(int s,int d1, int d2){
    //cout << s << " " << k-d1-d2 << endl;
    ans*=max(k-d1-d2,0);
    ans%=mod;
    used[s] = true;
    int m=0;
    rep(i,G[s].size()){
        if (used[G[s][i]]) continue;
        dfs(G[s][i],1,d1+m);
        m+=1 ;
    }
}

int main(){
    cin >> n >> k;
    rep(i,n) used[i] = false;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    // rep(i,n){
    //     rep(j,G[i].size()){
    //         cout << i << " " << G[i][j] << endl;
    //     }
    // }
    dfs(0,0,0);
    cout << ans << endl;
}

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

long long Map[200][200] = {};
 
int main(){
    int N,M,R;
    cin >> N >> M >> R;
    vector<int> r(R);
    rep(i,R){
        cin >> r[i];
        r[i]--;
    }

    rep(i,N){
        rep(j,N){
            if(i==j) Map[i][j] = 0;
            else Map[i][j] = 1e9;
        }
    }

    rep(i,M){
        int A,B,C;
        cin >> A >> B >> C;
        A--,B--;
        Map[A][B] = C;
        Map[B][A] = C;
    }

    rep(k,N){
        rep(i,N){
            rep(j,N){
                Map[i][j] = min(Map[i][j],Map[i][k] + Map[k][j]);
            }
        }
    }

    long long res = LONG_LONG_MAX;
    sort(r.begin(),r.end());
    do {
        long long sum = 0;
        rep(i,R-1){
            sum += Map[r[i]][r[i+1]];
        }
        res = min(res,sum);

    } while (std::next_permutation(r.begin(), r.end()));

    cout << res << endl;

    return 0;
}

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

using namespace std;

int main(){
 int stone = 0;
 vector<char> str(3);
 
 cin >> str.at(0) >> str.at(1) >> str.at(2);
 
 for (int i = 0; i < 3; i++){
   if (str.at(i) == '1') stone++;
 }
 
 cout << stone << endl;
}


Measured memory_bytes: 256
import numpy as np
a = int(input())
ary = np.array(list(input().split()), dtype=int)

def is_all_even(nums):
    return (nums % 2 == 0).all()

count = 0
while True:
    if not is_all_even(ary):
        print(count)
        break
    else:
        count += 1
        ary //= 2

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

#define SIZE 300005
#define MOD 1000000007LL
#define INF INT_MAX / 3
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define FORALL(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FOREACH(i,c) for(auto (i) : (c))
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef valarray<int> Array;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cout<<a[i];if(i==a.size()-1)cout<<endl;else cout<<" ";}}
int gcd(int a,int b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
int lcm(int a,int b){return a==0||b==0?0:a*b/gcd(a,b);}

map<string, int> generate(vector<int> v)
{
  map<string, int> T;
  if(v.size() == 1)
  {
    if(v[0] < 0) T["("+to_string(v[0])+")"] = v[0];
    else T[to_string(v[0])] = v[0];
    return T;
  }
  else
  {
    REP(i,v.size()-1)
    {
      vector<int> a,b;
      map<string, int> s,t;
      FOR(j,0,i) a.push_back(v[j]);
      FOR(j,i+1,v.size()-1) b.push_back(v[j]);
      s = generate(a);
      t = generate(b);
      for(auto m : s) for(auto n : t)
      {
        T["("+m.first+" * "+n.first+")"] = m.second * n.second;
        T["("+m.first+" + "+n.first+")"] = m.second + n.second;
        T["("+m.first+" - "+n.first+")"] = m.second - n.second;
      }
    }
    return T;
  }
}

void solve(vector<int> v)
{
  do
  {
    map<string, int> T = generate(v);
    for(auto a : T) if(a.second == 10)
    {
      printf("%s\n",a.first.c_str());
      return;
    }
  } while(next_permutation(v.begin(),v.end()));
  printf("0\n");
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<int> a(4);
  // FOR(i,1,9)FOR(j,1,9)FOR(k,1,9)FOR(l,1,9)
  // {
  //   a[0] = i; a[1] = j; a[2] = k; a[3] = l;
  //   solve(a);
  // }
  while(1)
  {
    REP(i,4) cin >> a[i];
    if(!accumulate(a.begin(),a.end(),0)) break;
    sort(a.begin(),a.end()); solve(a);
  }
  return 0;
}

Measured memory_bytes: 3168
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<stack>
#include<sstream>
using namespace std;
 
string s;
int vis[200005];
int main()
{
	cin >> s;
	long long num = 0;
	int a = 1,cnt = 0;
	vis[0] = 1;//余数为零直接cnt++不用找出余数相同的数
	for (int i = s.size() - 1; i >= 0; i--)
	{
		num = (num + a * (s[i] - '0') % 2019) % 2019;
		a = a * 10 % 2019;
		cnt += vis[num];
		vis[num]++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3708
n = int(input())
S = set()
ans = []
for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        S.add(cmd[1])
    elif cmd[0] == 'find':
        if cmd[1] in S:
            ans.append('yes')
        else:
            ans.append('no')
for a in ans:
    print(a)


Measured memory_bytes: 35280
use std::str::FromStr;
use std::io::*;
use std::collections::*;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}
#[derive(Copy, Clone, Hash, Eq, PartialEq)]
struct S {
    s: usize, // 駅
    c: usize, // 運営会社
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = AtRead::from(i);
    let (n, m) = i.read2::<usize, usize>();

    let mut edges = vec![Vec::new(); n];
    for _ in 0..m {
        let (p, q, c) = i.read3::<usize, usize, usize>();
        let (p, q) = (p - 1, q - 1);
        edges[p].push(S { s: q, c: c });
        edges[q].push(S { s: p, c: c });
    }
    let result = if let Some(cost) = solve(n, &edges) {
        format!("{}", cost)
    } else {
        "-1".to_string()
    };
    writeln!(o, "{}", result).unwrap();
}
fn solve(n: usize, edges: &[Vec<S>]) -> Option<usize> {
    let mut costs = vec![usize::max_value(); n];
    let mut s = (HashSet::new(), HashSet::new());
    let mut visits = HashSet::new();
    let mut q = Vec::new();
    s.0.insert(0);
    costs[0] = 0;

    for cost in 1.. {
        if s.0.is_empty() {
            return None;
        }
        for &s0 in &s.0 {
            for &sc in &edges[s0] {
                q.push(sc);
            }
        }
        visits.clear();
        while let Some(sc0) = q.pop() {
            if costs[sc0.s] < cost || !visits.insert(sc0) {
                continue;
            }
            if sc0.s == n - 1 {
                return Some(cost);
            }
            s.1.insert(sc0.s);
            costs[sc0.s] = cost;
            for &sc1 in &edges[sc0.s] {
                if sc1.c == sc0.c {
                    q.push(sc1);
                }
            }
        }
        s.0.clear();
        s = (s.1, s.0);
    }
    unreachable!()
}

mod utils {
    use super::*;

    pub struct AtRead<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        {$f:ident($($v:ident: $t:ident),*)} => {
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                $(
                    let $v = next(i);
                )*
                ($($v),*)
            }
        };
    }

    impl<R: BufRead> AtRead<R> {
        pub fn from(r: R) -> Self {
            AtRead {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        fn_read! { read2(v1: T1, v2: T2) }
        fn_read! { read3(v1: T1, v2: T2, v3: T3) }
    }

    fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }
}


Measured memory_bytes: 38592
import sys
sys.setrecursionlimit(300000)
from itertools import combinations

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
L = LMI()

ans = 0
for a, b, c in combinations(L, 3):
    if a == b or b == c or c == a:
        continue
    if a + b > c and b + c > a and c + a > b:
        ans += 1
print(ans)


Measured memory_bytes: 73344
module.exports=function(e){var t={};function n(r){if(t[r])return t[r].exports;var o=t[r]={i:r,l:!1,exports:{}};return e[r].call(o.exports,o,o.exports,n),o.l=!0,o.exports}return n.m=e,n.c=t,n.d=function(e,t,r){n.o(e,t)||Object.defineProperty(e,t,{enumerable:!0,get:r})},n.r=function(e){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(e,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(e,"__esModule",{value:!0})},n.t=function(e,t){if(1&t&&(e=n(e)),8&t)return e;if(4&t&&"object"==typeof e&&e&&e.__esModule)return e;var r=Object.create(null);if(n.r(r),Object.defineProperty(r,"default",{enumerable:!0,value:e}),2&t&&"string"!=typeof e)for(var o in e)n.d(r,o,function(t){return e[t]}.bind(null,o));return r},n.n=function(e){var t=e&&e.__esModule?function(){return e.default}:function(){return e};return n.d(t,"a",t),t},n.o=function(e,t){return Object.prototype.hasOwnProperty.call(e,t)},n.p="",n(n.s=0)}([function(e,t,n){n(1)(n(2).readFileSync("/dev/stdin","UTF-8"))},function(e,t){e.exports=function(e){for(var t=e.split("\n")[0],n=t.length,r=0,o=0;o<n;o++)0==t[o]&&(r+=1);var u=2*Math.min(r,n-r);console.log(u)}},function(e,t){e.exports=require("fs")}]);

Measured memory_bytes: 7500
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define repm(i,a,b) for(ll i=(ll)(a);i>(ll)(b);i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(),(x).rend()
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vc vector<char>
#define vvc vector<vc>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;
using vb =vector<bool>;
using vvb=vector<vb>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
//snippets:tmp,cl,cvl,cs,co,coy,con,cov,setp

int main(){
    ll n;
    cin >> n;
    ll k;
    cin >> k;
    vll p(n);
    rep(i, n) cin >> p[i];
    sort(all(p));
    ll ans=0;
    rep(i,k) ans+=p[i];
    cout << ans << endl;
}

Measured memory_bytes: 3536
#include <stdio.h>
#define NIL -2000000001
 
int main(void){
  int i,h;

  scanf("%d",&h);

  int heap[h+1];
  for(i=0; i<=h; i++)
    heap[i] = NIL;
 
  for(i=1; i<=h; i++)
    scanf("%d",&heap[i]);
 
  for(i=1; i<=h; i++){
    printf("node %d: ",i);
    printf("key = %d, ",heap[i]);
    if(heap[i/2]!=NIL && i/2<=h && i/2>=0)
      printf("parent key = %d, ",heap[i/2]);
    if(heap[2*i]!=NIL && 2*i<=h && 2*i>=0)
      printf("left key = %d, ",heap[2*i]);
    if(heap[2*i+1]!=NIL && 2*i+1<=h && 2*i+1>=0)
      printf("right key = %d, ",heap[2*i+1]);
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 600
#include <stdio.h>

int main(int argc, char *argv[]){
  int n;
  
  while(scanf("%d",&n) != EOF){
    int d = 0;

    if(n == 0){break;}
    
    while(n /= 5){
      d += n;
    }
    
    printf("%d\n",d);
    
  }
  
  return 0;    
}

Measured memory_bytes: 0
import java.util.*;
public class Main {
    static int mod = 1000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        long all = exp(2, n);
        all = xmod(all - 1);
        long nca, ncb;
        nca = frac(n, a) * modInv(frac(a, a)) % mod;
        ncb = frac(n, b) * modInv(frac(b, b)) % mod;
        all = xmod(all - nca);
        all = xmod(all - ncb);
        System.out.println(all);
    }
    public static long exp(long i, long j) {
        if (j == 0) return 1;
        if (j == 1) return i;
        long k = exp(i, j / 2) % mod;
        long r = 1;
        if (j % 2 == 1) r = i;
        return (k * k % mod) * r % mod;
    }
    public static long xmod(long a) {
        return (a % mod + mod) % mod;
    }
    public static long frac(long a, long b) {
        long s = a;
        long ret = 1;
        while (s > a - b) {
            ret = ret * s % mod;
            s--;
        }
        return ret;
    }
    public static long modInv(long n) {
        long s = n, t = mod, u = 1, w = 0;
        while (t > 0) {
            long q = s / t;
            long temp;
            s %= t; temp = s; s = t; t = temp;
            u -= q * w; temp = u; u = w; w = temp;
        }
        return (u % mod + mod) % mod;
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;

int main(){
  int res = 0; int N; cin >> N;
  vector<int> d(N);
  for(int i=0; i<N; i++) cin >> d[i];

  for(int i=0; i<N; i++){
    for(int j=0 ; j<i; j++){
      res += d[i] * d[j];
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	String r = "yuiophjklnm";
	
	boolean find(char c) {
		for(int i=0;i<r.length();i++)
			if(r.charAt(i) == c) return true;
		return false;
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			String str = sc.next();
			if(str.equals("#")) break;
			int cnt=0;
			for(int i=0;i<str.length()-1;i++)
				cnt += find(str.charAt(i))^find(str.charAt(i+1))? 1:0;
			System.out.println(cnt);
		}
	}

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

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
N = int(input())
S = [0]*N

for i in range(N):
    S[i] = input()

print("AC x {}".format(S.count('AC')))
print("WA x {}".format(S.count('WA')))
print("TLE x {}".format(S.count('TLE')))
print("RE x {}".format(S.count('RE')))

Measured memory_bytes: 16040
def d_wall(H, W, C, A):
    cost=C
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += cost[A[i][j]][1]
    return ans

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Measured memory_bytes: 40432
#include <iostream>
#include <cmath>

using namespace std;

long long digit(long long n){
	int ans = 0;
	while(n!=0){
		n /= 10;
		ans++;
	}
	return ans;
}

int main(){
	long long i,n,ans = 20,x;
	cin >> n;
	for(i=1;i<=sqrt(n);i++){
		if(n%i==0){
			x = max(digit(i),digit(n/i));
			ans = min(x,ans);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<int> arr(N);
	for (auto&i : arr)std::cin >> i;
	std::sort(arr.begin(), arr.end());
	int ans = INT_MAX;
	for (int i = 0; i < N - K + 1; ++i)ans = std::min(ans, arr[i + K - 1] - arr[i]);
	std::cout << ans << std::endl;
}


Measured memory_bytes: 640
n = int(input())
ans = 0
hoges = []
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  # for k in range(max(1, 0), len(currents)):
  for k in range(max(1, len(currents) - 3), len(currents)):
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v
memo = {}
ng_memo = {} # 後ろ4つだけ見ればNGわかる？
def f(index, currents):
  ng_key = currents[-4:]
  key = '%d:%s' % (index, currents[-4:])
  # print(key)
  if ng_key in ng_memo:
    return 0
  if key in memo:
    return memo[key]
  if ng(currents):
    ng_memo[key] = True
    return 0
  if index == n:
    return 1
  memo[key] = sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print(f(0, '') % int(1e9+7))

# 3:      61
# 4:     230
# 5:     865
# 6:    3247
# 7:   12185
# 8:   45719


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

class Cube{
public:
 int f[6];
 Cube(){}
 void roll_z(){ roll(1,2,4,3);} //
 void roll_y(){ roll(0,2,5,3);} // to W
 void roll_x(){ roll(0,1,5,4);} // to N
 void roll(int i, int j, int k, int l){
  int t=f[i]; f[i]=f[j]; f[j]=f[k]; f[k]=f[l]; f[l]=t;
 }
};

int getRight(Cube c1, int f1, int f2){
 for(int i=0;i<6;i++){
  for(int j=0;j<4;j++){
   if(c1.f[0]==f1 && c1.f[1]==f2) return c1.f[2];
   c1.roll_z();
  }
  if(i%2==0) c1.roll_y();
  else c1.roll_x();
 }
 return -1;
}

int main(){
 Cube c;
 int f1,f2;

 for(int i=0;i<6;i++)cin >> c.f[i];
 int q; cin >> q;

 for(int i=0;i<q;i++){
  cin >> f1 >>f2;
  cout << getRight(c,f1,f2) << endl;
 }

 return 0;
}

Measured memory_bytes: 1160
import sys
input = sys.stdin.buffer.readline

T = int(input())


def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
def init_min(init_min_val):
    #set_val
    for i in range(n):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_max = -1
#####単位元######
ide_ele_min = 10**10


dg = 10**6

for testcase in range(T):
    n = int(input())
    #num_max:n以上の最小の2のべき乗
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max
    #num_min:n以上の最小の2のべき乗
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min
    init_min(list(range(n)))
    init_max(list(range(n)))

    res = 0
    tank = []
    res = 0
    for i in range(n):
        K,L,R = map(int,input().split())
        K -= 1
        if L <= R:
            tank.append((R-L)*dg+K*2+1)
            res += L
        else:
            tank.append((L-R)*dg+K*2)
            res += R
    tank.sort(reverse = True)
    s = 0
    for e in tank:
        pt,amari = divmod(e,dg)
        idx,right = divmod(amari,2)
        if right == 0:
            kk = query_max(0,idx+1)
            if kk != -1:
                res += pt
                update_max(kk,-1)
        else:
            kk = query_min(idx+1,n)
            if kk != 10**10:
                res += pt
                update_min(kk,10**19)

    print(res)

Measured memory_bytes: 102404
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define OUTPUT(x) (output(x), output("\n"))
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
        if(b&1)res = res * x % MOD;
        x = x * x % MOD;
        b>>=1;
    }
    return res;
}

ll modinv(ll x){
    return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
}
void outendl(){
    was_output = false;
    cout << endl;
}
ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
}

template<class t>
istream& operator>>(istream& is, vector<t> &x){
    for(auto &i:x)is >> i;
    return is;
}

template<class t, class u>
istream& operator>>(istream& is, pair<t, u> x){
    is >> x.first >> x.second;
    return is;
}


int main(){
    int n;
    cin >> n;
    cout << (n+1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
<?php
  $n = trim(fgets(STDIN));
  $p = explode(" ", trim(fgets(STDIN)));
  $cnt = 0;
  $ans = 0;
  for($i=0; $i<$n; $i++){
      if($p[$i]-1 == $i){
          $cnt++;
          
          if($i == $n-1){
              if($cnt > 1){
                  $ans += ceil($cnt/2);
              } else {
                  $ans += $cnt;
              }
          }
      }else{
          if($cnt > 1){
              $ans += ceil($cnt/2);
          } else {
              $ans += $cnt;
          }
          $cnt=0;
      }
  }
  echo $ans;

Measured memory_bytes: 23504
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String [] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long array[] = new long[n];
        String temp[] = br.readLine().split(" ");
        long ans = 1;
        long maxValue =1000000000000000000l;
        for(int i=0;i<n;i++){ 
            array[i] = Long.parseLong(temp[i]);
            if(array[i]==0) {System.out.println(0); return;}
        }

        for(int i=0;i<n;i++){ 
        
            if(array[i]<=(maxValue/ans)) {
                ans = ans*array[i];
            }
            else {
                System.out.println(-1);
                return;
            }
        }


        System.out.println(ans);
       

    }
}

Measured memory_bytes: 50024
#include <bits/stdc++.h>
using namespace std;
#define lli long long
int ans,cnt=0;
int a[200004];
vector<int> adj[200004];
bool vis[200004];

void dfs(int node,int k) {
    if(k==0) {
        ans = node;
        return;
    }
    
    for(int v:adj[node]) {
        dfs(v,k-1);
    }
}

int length(int u,int node) {
    
    if(u==node) return 0;
    
    return 1+length(adj[u][0],node);
}

int main() 
{
    lli n, k;
    
    cin >> n >> k;
    
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    
    int u = 1;
    int i = 1;
    lli cnode, total = 0;
    
    while(1){
        int v = a[i];
        
        adj[u].push_back(v);
        
        if(vis[v])  {
            cnode = v;
            total++;
            break;
        }
        
        vis[u] = true;
        i = a[i];
        u = v;
        
        total++;
    }
    
    //cout<<cnode<<" "<<total<<endl;
    if(cnode==1) {
        k = (k%total);
        dfs(cnode,k);
    } else{
        if(k>total) {
            //cout<<length(1,cnode)<<endl;
            k -= (1LL*length(1,cnode));
            total -= (1LL*length(1,cnode));
            k = (k%total);
            dfs(cnode,k);
        }
        else{
            dfs(1,k);
        }
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 19812