akhauriyash/Code-Regression huggingface dataset:
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

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

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    bool isGood = true;
    REP(i, 3){
        if(s[i] == s[i+1]){
            isGood = false;
        }
    }
    if(isGood){
        cout << "Good" << endl;
    }
    else {
        cout << "Bad" << endl;
    }
    return 0;
}

Measured memory_bytes: 888
def main(X,A,N):
    for i in range(N-1):
        X[i+1] = 2*A[i] - X[i]
    return X
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
Aoddsum = sum(A[1:N:2])
X1 = S - 2*Aoddsum
X = [0]*N
X[0] = X1
main(X,A,N)
print(" ".join(list(map(str, X))))



Measured memory_bytes: 19148
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 = []
    if len(x) == 0:
        return []
    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 pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
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 = onem()

a,b = 1,1

for i in range(n):
    x,y = m()
    po = max(-(-a//x),-(-b//y))
    a = po*x
    b = po*y

print(a+b)




Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);

	int x;
	cin >> x;
	int i=1;
	while (x != 0) {
		cout << "Case " << i << ": " << x << "\n";
		i++;
		cin >> x;
	}
}


Measured memory_bytes: 3008
#ABC141-B Tap Dance
S = list(input())
def oddschange(s):
    if s == 'L':
        return 0
    else:
        return 1
def evenchange(s):
    if s == 'R':
        return 0
    else:
        return 1
ans = 1
for i,s in enumerate(S):
    if i %2 == 0:
        ans *= oddschange(s)
    else:
        ans *= evenchange(s)
print('Yes') if ans else print('No')

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.ExceptionServices;
using System.Runtime.InteropServices;
using System.Text;


namespace AtCoderDotNetCore
{
	class Program
	{
		static void Main(string[] args)
		{
			Question.Exec();
		}
	}

	public static class Question
	{
		public static void Exec()
		{
			long n = long.Parse(Console.ReadLine());
			var a = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();


			if (n % 2 == 1) {
				for (var i = n - 1; i >= 0; i = i - 2) {
					Console.Write($"{a[i]}");
					Console.Write(" ");
				}

				for (var i = 1; i < n - 1; i = i + 2) {
					Console.Write($"{a[i]}");

					if (i < n - 1 - 1) {
						Console.Write(" ");
					} else {
						Console.WriteLine();
					}
				}
			} else {
				for (var i = n - 1; i >= 1; i = i - 2) {
					Console.Write($"{a[i]}");
					Console.Write(" ");
				}

				for (var i = 0; i < n; i = i + 2) {
					Console.Write($"{a[i]}");

					if (i < n - 1) {
						Console.Write(" ");
					} else {
						Console.WriteLine();
					}
				}
			}
		}
	}
}

Measured memory_bytes: 57176
#include<bits/stdc++.h>
using namespace std;
bool ham[1000001];
int main(){
  ham[1]=1;
  for(int i=0;i<1000001;i++)
    if(ham[i]){
      if(i*2<=1000000)ham[i*2]=1;
      if(i*3<=1000000)ham[i*3]=1;
      if(i*5<=1000000)ham[i*5]=1;
    }
  int x,y;
  while(cin>>x,x){
    cin>>y;
    int sum=0;
    for(int i=x;i<=y;i++)
      if(ham[i])sum++;
    cout<<sum<<endl;
  }
}

Measured memory_bytes: 3708
#include<stdio.h>
#define N 100001
#define NIL -1
 
 struct Node
{
  int parent;
  int left;
  int right;
};
struct Node T[N];
int cnt=0;
 
int depth(int nodeid)
{
  if(T[nodeid].parent == NIL) 
  {
    return cnt;
  }
  else
  {
 cnt++;
 return depth(T[nodeid].parent);
  }
}
 
void degree(int nodeid)
{
  if(nodeid != NIL)
  {
    if(cnt != 0)
    {
      printf(", ");
    }
    printf("%d",nodeid);
    cnt++;
    degree(T[nodeid].right);
  }
} 
 
int main(void) 
{
   
  int i,j,n,m,newnode,child,left,right;
   
  scanf("%d",&n);
 
  for(i=0;i<n;i++)
    T[i].parent = T[i].left = T[i].right = NIL;
 
  for(i=0;i<n;i++)
  {
    scanf("%d%d",&newnode,&m);
    for(j=0;j<m;j++)
    {
      scanf("%d",&child);
      T[child].parent = newnode;
      if(j != 0) {
    T[left].right = child;
      }
      else {
    T[newnode].left = child;
      }
      left = child;
    }
  }
  for(i=0;i<n;i++) {
    cnt = 0;
    printf("node %d: parent = %d, depth = %d, ",i,T[i].parent,depth(i));
      if(T[i].parent == NIL) {
    printf("root, [");
      }
      else if (T[i].left == NIL) {
    printf("leaf, [");
      } 
      else  {
    printf("internal node, [");
      }   
    cnt=0;
    degree(T[i].left);
    printf("]\n");
  }
  return 0;
}

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

using namespace std;

int main(){
    int n;
    long long x;
    cin >> n >> x;
    vector<int> m(n);
    for (int i = 0; i < n; i++) cin >> m.at(i);
    
    int sumM = 0;
    int curMin = 9999;
    for (int i = 0; i < n; i++){
        sumM = sumM +  m.at(i);
        curMin = min(curMin, m.at(i));
    }
    
    
    int lastX = x - sumM;
    int count = lastX / curMin;
    int ans = n + count;
    
    cout << ans << endl;
    

}

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

int main() {
    string s;//文字列型変数sを宣言
    cin >> s;//文字列sに入力
    int size = s.size();//文字列sの長さを取得しint型変数sizeを宣言し長さを格納
    cout << s.at(0) << size - 2 << s.at(size - 1) << endl;
}


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

k, n = map(int, input().split())
a = list(map(int,input().split()))

table =[-1] * len(a)

for i in range(len(a)):
    if i < len(a) - 1:
        table[i] = a[i+1] - a[i]
    else:
        table[i] = a[0] + k - a[len(a)-1]
table.remove(max(table))

print(sum(table))


Measured memory_bytes: 26444
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] Weight = new int[n];
        for(int i = 0; i < n; i++){
            Weight[i] = sc.nextInt();
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum = sum + Weight[i];
        }
        int subsum = 0;
        int sub = 0;
        int submin = sum;
        for(int i = 0; i < n; i++){
            subsum = subsum + Weight[i];
            sub = Math.abs((sum - subsum) - subsum);
            if(sub < submin){
                submin = sub;
            }
        }
        System.out.print(submin);
    }
}

Measured memory_bytes: 21332
#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 100010
#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)

inline void read( int &x ){
    x = 0 ; int f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    x *= f ;
}

inline void readl( ll &x ){
    x = 0 ; ll f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    x *= f ;
}

using namespace std ;

int n , m , a[ N ] ;

int main(){
	for( int i = 1 ; i <= 3 ; i ++ ) {
		in1(a[i]);
	}
	sort(a+1,a+4);
	printf("%d\n",a[3]*10+a[2]+a[1]);
}

Measured memory_bytes: 128
#include<stdio.h>
#include<algorithm>
int main()
{
	int n,i,a[100],u,v,w,x,y;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d%d%d%d%d",&u,&v,&w,&x,&y),a[i]=u+v+w+x+y;
		std::sort(a,a+n);
		printf("%d %d\n",a[n-1],a[0]);
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=1e9,dx[]={-1,0,1,0},dy[]={0,-1,0,1};
const long long llinf=1e18;
const int A=100005,B=200005,C=305,D=105,E=1005,F=3005;
int a[3],minv;
int main(){
	cin>>a[0]>>a[1]>>a[2];
	minv=inf;
	do
	{
		minv=min(minv,abs(a[0]-a[1])+abs(a[1]-a[2]));
	}while(next_permutation(a,a+3));
	cout<<minv;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++)
  {
    cin>>s[i];
  }
  map<string ,int>str;
  for(int i=0;i<n;i++)
  { 
    ++str[s[i]];
  }
  int count=0;
  for(auto it=str.begin();it!=str.end();it++)
  {
    if(it->second == 1)
    {
      count++;
    }
  }
  if(count == str.size())
    {
      for(auto it=str.begin();it!=str.end();it++)
        cout<<it->first<<endl;
    }
  else
  {
  //string arg_max = " "; 
  int current_max=0;
  for(auto it=str.begin();it!=str.end();it++)
  {
    if(it->second > current_max)
    {
    	//arg_max = it->first;
      	current_max = it->second;
    }
  }
  for(auto it=str.begin();it!=str.end();it++)
   {
    if(it->second == current_max)
  //cout<<arg_max;
      cout<<it->first<<endl;
   }
  }
 // auto max=get_max(str);
//std::cout << max.first; //<< "=>" << max.second << std::endl; 
 // }
  return 0;
}																																																											

Measured memory_bytes: 26752
import sys 
input = sys.stdin.readline

n = int(input())
p = [float(x) for x in input().split()]

dp = [[0]*(n + 1) for _ in range(n + 1)]
dp[0][0] = 1

ans = 0

for i in range(1, n + 1):
    p_i = p[i - 1]
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] * (1 - p_i)
        if j - 1 >= 0:
            dp[i][j] += dp[i - 1][j - 1] * (p_i)
        if i == n and j > (i - j):
            ans += dp[i][j]

print(ans)


Measured memory_bytes: 253320
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    s = IS()
    if s[0] == 'R' and s[1] == 'R' and s[2] == 'R':
        print(3)
    elif s[0] == 'R' and s[1] == 'R':
        print(2)
    elif s[1] == 'R' and s[2] == 'R':
        print(2)
    elif s[0] == 'R' or s[1] == 'R' or s[2] == 'R':
        print(1)
    else:
        print(0)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9148
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;

    int ans = 10e6;
    vector<int> black(N+1, 0);
    for(int i = 0; i < N; i++){
        if(S[i] == '#'){
            black[i+1] = black[i] + 1;
        }else{
            black[i+1] = black[i];
        }
    }
    for(int i = 0; i <= N; i++){
        ans = min(ans, black[i] + N - i - (black[N]-black[i]));
    }

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

Measured memory_bytes: 1412
from itertools import product as pro

n = int(input())
s = str(input())

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = len(r) * len(g) * len(b)

length = max(len(r), len(g), len(b))
for i, j, k in [(r, g, b), (g, b, r), (b, r, g)]:
    if length == len(i):
        max1 = set(i)
        min1, min2 = j, k

for i, j in pro(min1, min2):
    if 2*j-i in max1:
        cnt -= 1
    if 2*i-j in max1:
        cnt -= 1
    if (i+j)/2 in max1:
        cnt -= 1

print(cnt)

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

int a[200050];

int main(){

    int n;
    cin >> n;
    int s = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        s = s^a[i];
    }

    for(int i=0;i<n;i++){
        int ans = s^a[i];
        if(i==n-1)
            cout << ans << endl;
        else
            cout << ans << " ";
    }
}


Measured memory_bytes: 4348
///supercalifragilisticexpialidocious.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <utility>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <bitset>
#include <complex>
using namespace std;
#define f first
#define s second
#define PB pop_back 
#define pb push_back
#define mp make_pair
#define int long long
#define y1 y_golabi
#define sz(s) (int)s.size()
#define seper(n) setprecision(n)
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a,b,sizeof a)
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef map<int , int> mii;
typedef pair<int , int> pii;
typedef map<string , int> msi;
typedef pair<int , string> pis;
typedef pair<int , pair<int , int> > piii;
const int MAXN = 1e5 + 10;
int n , ans , b[MAXN];
pii a[MAXN];
int32_t main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i ++)
		cin >> a[i].f , a[i].s = i;
	sort(a , a + n);
	for(int i = 0 ; i < n ; i ++)
		b[a[i].s] = i;
	for(int i = 1 ; i < n ; i += 2)
		ans += (!(b[i] & 1));
	return cout << ans << endl , 0;
}
	


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
#define  double long double
#define mod 1000000007
#define pi acos(-1)
using namespace std;

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

    string s, t;
  cin >> s >> t;
  int ans = 3;
  for(int i = 0 ; i < 3; i ++){
    if(s[i] != t[i]){
      ans--;
    }
  }
  cout << ans;
    return 0;
}


Measured memory_bytes: 256
S = str(input())
Q = int(input())

head = ""
tail = ""
main = S

status = 0

while Q:
  Q -= 1
  l = list(map(str,input().split()))
  if l[0] == "1":
    status = (status+1)%2
  else:
    letter = l[2]
    if l[1] == "1":
      if status == 0:
        head += letter
      else:
        tail += letter
    else:
      if status == 0:
        tail += letter
      else:
        head += letter

if status == 0:
  print(head[::-1]+main+tail)
else:
  print(tail[::-1]+main[::-1]+head)


Measured memory_bytes: 4412
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

bool cc[1000][10000];
int main()
{
	while(1)
	{
		int n,m;
		cin>>n>>m;
		if(m==0)
			break;
		int s[1000];
		int k[1000];
		fill(cc[0],cc[1000],false);
		for(int i=0;i<m;i++)
		{
			cin>>s[i];
			cin>>k[i];
			for(int j=0;j<k[i];j++)
			{
				int c;
				cin>>c;
				c--;
				cc[i][c]=true;
			}
		}

		//それぞれの人間が取りうる最高点と最低点を調べる
		ll score[10000][2];
		for(int i=0;i<n;i++)
		{
			score[i][0]=0;
			score[i][1]=0;//最低点
			for(int j=0;j<m;j++)
			{
				//もしiしか正解できない問題ならiが取らなくてはならない
				if(cc[j][i] && k[j]==1)
					score[i][1]+=s[j];
				
				if(cc[j][i])
					score[i][0]+=s[j];
			}
		}

		ll ans=0;
		//iが最高点を取りjが最低点を取ったときの点差を調べる
		for(int i=0;i<n;i++)
		{
			//cout<<score[i][0]<<" "<<score[i][1]<<endl;//fordebug
			for(int j=0;j<n;j++)
			{
				if(i==j)
					continue;
				ans=max(ans,score[i][0]-score[j][1]);
			}
		}
		ans++;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 13044
#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

ll MOD = 1e9 + 7;

ll calc_pow(ll x, ll pow) {
    if (pow <= 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % MOD;
    if (pow % 2 == 1) a *= x;
    return a % MOD;
}

int main() {
    string s;
    cin >> s;

    int back = 0;
    ll ret = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') {
            ret += calc_pow(2, back) * calc_pow(3, s.size() - 1 - i);
            ret %= MOD;
            back++;
        }
    }

    ret += calc_pow(2, back) * calc_pow(3, 0) % MOD;
    cout << ret % MOD << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() ;
const ll linf = numeric_limits<ll>::max() ;
const ull ulinf = numeric_limits<ull>::max();
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){
	int n,m,r;
	cin >> n >> m >> r;
	int f[10] = {};
    rep(i,0,r)cin >> f[i];

    sort(f,f+r);
    ll d[205][205] = {};
    rep(i,1,n+1)rep(j,1,n+1)if(i != j)d[i][j] = linf/2;
    rep(i,0,m){
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = c;
        d[b][a] = c;
    }

    rep(k,1,n+1)
        rep(i,1,n+1)
            rep(j,1,n+1)d[i][j] = min(d[i][j],d[i][k] + d[k][j]);

    ll ans = linf/2;
    do{
        ll tmp = 0;
		rep(i,1,r){
            tmp += d[f[i-1]][f[i]];
		}
		ans = min(ans,tmp);
		 	
	}while(next_permutation(f,f+r));

    P(ans);

	return  0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
	int b[10000]={0};
	for(int i=0;i<=100;i++){
		for(int j=0;j<=100;j++){
			b[i*7+4*j]=1;
		}
	}
	int n;
	cin>>n;
	if(b[n] == 1){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    A.sort()
    print(sum(A[:K]))





if __name__ == "__main__":
    main()

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

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

using ll = long long int;
using P = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VB = vector<bool>;
using VVB = vector<VB>;




int main(){
  int n, y;
  scanf("%d%d",&n,&y);
  y /= 1000;
  int a, b, c;
  a = -1;b = -1; c = -1;
  for(int i = 0;i <= n;i++){
    for(int j = 0;j <= (n - i);j++){
      if(9 * i + 4 * j == (y - n)){
        a = i; b = j; c = (n - i - j);
        i = n;j = 0; // to break this loop
      }
    }
  }
  printf("%d %d %d\n",a,b,c);
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Deque<String> q = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            String c = sc.next();
            if(i % 2 == 0){
                q.addLast(c);
            }else{
                q.addFirst(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        if(n % 2 != 0){
            while(q.size() != 0){
                System.out.print(q.pollLast() + " ");
            }
        }else{
            while(q.size() != 0){
                System.out.print(q.pollFirst() + " ");
            }
        }
    }
}

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

int N, M, X, Y, x[109], y[109], ret1, ret2;

int main() {
	cin >> N >> M >> X >> Y; ret1 = X; ret2 = Y;
	for (int i = 0; i < N; i++) { cin >> x[i]; ret1 = max(ret1, x[i]); }
	for (int i = 0; i < M; i++) { cin >> y[i]; ret2 = min(ret2, y[i]); }
	if (ret1 < ret2) cout << "No War" << endl;
	else cout << "War" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

const int MAX_V = 1000000;
int data[999999], sum[1000000];

int main() {
  int i, k, n;
  for(i = 2; i < MAX_V; i++) {
    data[i] = 1;   
  }
  for(i = 2; i * i < MAX_V; i++) {
    if(data[i] == 1) {
      for(k = 2 * i; k < MAX_V; k += i) {
        data[k] = 0;
      }
    }
  }
  for(i = 2; i < MAX_V; i ++) {
    sum[i + 1] = sum[i] + data[i];
  }
  while(scanf("%d", &n) != EOF) {
    printf("%d\n", sum[n + 1]);
  }
  return 0;
}

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

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

using namespace std;

//v.push_back(123);
//sort(v.begin(), v.end(),greater<int>());
//for(int x : v) {cout << x << endl;}

//for(int x: v) cout << x << endl;
//vector<vector<char>> v(H, vector<char>(W));
//vector<int> v(1000);

long long pow_mod(long long x, long long y, long long MOD){
	long long ret = 1;
	while(y){
		if (y & 1) ret = ret * x % MOD;
		x = x * x % MOD;
		y>>=1;
	}
	return ret;
}

signed main(){
  int X, A;
  cin>>X>>A;
  if(X<A){
    cout << 0 << endl;
  }else{
    cout << 10 << endl;
  }

  return 0;
}






Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
#define int long long
#define str string
typedef long long ll;
typedef long double ld;
const ll inf = 999999999999999999;
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {
	ll to, cost;
};
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int n, ans, t;
	cin >> n >> ans;
	for (int i = 1; i < n; i++) {
		cin >> t;
		ans = ans / gcm(t, ans)*t;
	}
	cout << ans << endl;
	getchar(); getchar();
}

Measured memory_bytes: 256
# /usr/bin/env python3
# https://atcoder.jp/contests/abc043/tasks/arc059_a

n = int(input())
a = [int(x) for x in input().split()]
ans = []
for i in range(min(a), max(a) + 1):
    ans.append(sum([(ax - i)**2 for ax in a]))
print(min(ans))


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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

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

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

struct UnionFind {
	vector<long long> par;
	UnionFind(long long size) : par(size+1, -1) { }
	bool unite(long long x, long long y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x;
		}
		return x != y;
	}
	bool same(long long x, long long y) {
		return root(x) == root(y);
	}
	int root(long long x) {
		return par[x] < 0 ? x : par[x] = root(par[x]);
	}
	int size(long long x) {
		return -par[root(x)];
	}
};

int main()
{
	ll n,m,k,a,b;
	cin >> n >> m >> k;
	UnionFind tree(n);
	vvll x(n+1),y(n+1);
	rep(i,m){
		cin >> a >> b;
		x[a].pb(b);
		x[b].pb(a);
		tree.unite(a,b);
	}
	rep(i,k){
		cin >> a >> b;
		y[a].pb(b);
		y[b].pb(a);
	}
	REP(i,1,n){
		ll tmp=tree.size(i)-x[i].size()-1;
		for(auto &e:y[i]){
			if(tree.same(i,e)) tmp--;
		}
		cout << tmp << (i==n?"\n":" ");
	}
	return 0;
}

Measured memory_bytes: 13684
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n;
	int a[100];
	int sum=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(i%2==0)
			sum+=a[i];
		else
			sum-=a[i];
	}
	printf("%d",sum);
	
}

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

int main(){
  int N;
  cin >> N;
  vector<int> Ans(N);
  int A;
  for(int i=0; i<N; i++){
    cin >> A;
    Ans.at(A-1)=i+1;
  }
  for(int i=0; i<N; i++){
    cout << Ans.at(i) << " ";
  }
}

Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();
		long res = Math.min(n, m / 2) + (m - Math.min(n, m / 2) * 2) / 4;
		System.out.println(res);
	}
}


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

int main(){
    int N,M;
    cin>>N>>M;
    vector<pair<long int,long int> > A(N);
    for(int i=0;i<N;i++){
        int B,C;
        cin>>B>>C;
        A[i]=make_pair(B,C);
    }
    sort(A.begin(),A.end());
    long long int C=0;
    for(int i=0;i<N;i++){
        if(M-A[i].second>0){
            M=M-A[i].second;
            C=C+A[i].first*A[i].second;
        }else{
            C=C+M*A[i].first;
            break;
        }
    }
    cout<<C<<endl;
}

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

int main() {
    int n, m, a, b;
    cin >> n >> m;
    bitset<200000> sima1, sima2;
    rep(i,m) {
        cin >> a >> b;
        if (a == 1) 
            sima1.set(b);
        if (b == n) 
            sima2.set(a);
    }

    if ((sima1&sima2).none())
        cout << "IMPOSSIBLE" << endl;
    else
        cout << "POSSIBLE" << endl;
    return 0;
}

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

int main() {
  int x,a,b;
  cin >> x >> a >> b;
  if (abs(x-a) > abs(x-b)) {
    cout << "B" << endl;
  }
  else {
    cout << "A" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define nmax 200
int psnum[nmax][3];
int point[nmax];
int n;
bool check(int a,int b) {
	int c=0;
	for (int i = 0; i < n; i++) {
		if (psnum[i][b] == a) {
			c++;
			if (c > 1)return false;
		}
	}
	return true;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> psnum[i][0] >> psnum[i][1] >> psnum[i][2];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			if (check(psnum[i][j], j))point[i] += psnum[i][j];
		}
	}
	for (int i = 0; i < n; i++)cout << point[i] << endl;
    return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define fi first
#define sec second
#define pr priority_queue
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s, t; cin >> s >> t;
	ll n = s.length(), m = t.length();
	ll i = 0, ct = LLONG_MAX;
	while (i <= n - m)
	{
		ll ans = 0;
		for (ll j = i; j < i + m; j++)
		{
			if (s[j] != t[j - i])
				ans++;
		}
		ct = min(ans, ct);
		i++;
	}
	cout << ct << "\n";
	return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<set>
#include<bitset>
#include<cmath>
#include<numeric>
#include<limits>

#define REP(i, m, n) for(int i = (m); i < (n); i++)
#define rep(i,n) REP(i,0,n)
#define NIL -1
using namespace std;
typedef long long ll;
typedef long long int lli;
static const int MOD = 10000007;
static const int MAX = 100005;


int N, K, Q;
string s;
int d[MAX];

int gcd(int a, int b) {
  if ( b > a ) swap(a, b);
  int r = 1;
  while (r > 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int main(){
  cin >> N >> K >> Q;
  rep(i, N) {
    d[i] = 0;
  }

  rep(i, Q) {
    int a; cin >> a;
    a--;
    d[a]++;
  }

  rep(i,N) {
    if ( Q - d[i] < K) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

string n;

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	if((n[0] == n[1] && n[0] == n[2]) || (n[1] == n[2] && n[1] == n[3])) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#require 'prime'
MOD=10**9+7;  cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.chomp.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def ar2(s1,s2,de=nil) Array.new(s1){Array.new(s2,de)} end
def ar3(s1,s2,s3,de=nil) Array.new(s1){Array.new(s2){Array.new(s3,de)}} end

def desc(ar) ar.sort!{|x,y| y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end
def ceil(a,b) (a.to_f/b).ceil end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end
def rui(ar) s=[0]; ar.size.times{|i| s<<s[-1]+ar[i]}; s end
def rev_rui(ar) s=[0]; ar.size.times.reverse_each{|i| s<<s[-1]+ar[i]}; s end

def puts_yesno(b) puts(b ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def pu(h) begin; require './../nemi_lib/debug.rb'; puts_val(h); rescue LoadError; end; end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n=gi
a=gsmi
a.each do |i|
  h[i]+=1
end
#puts h.to_a.to_s

all=0
h.to_a.each do |k,v|
  next if v<=1
  all+=C(v,2)
end 

ans=[]
n.times do |i|
  v=h[a[i]]
  ans<<all+(v<=1 ? 0 : (v==2 ? 0 : C(v-1,2))-C(v,2))
end
puts ans

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

using namespace std;
int main() {
	int n;
	int now = 1;
	int tmp;
	int brick = 0;
	cin >> n;
	vector<int> a(n),s(n);

	
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (now == tmp) {
			now++;
		}
		else {
			brick++;
		}
	}
	if (brick == n) {
		brick = -1;
	}
	cout << brick;

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
constexpr char NL = '\n';
constexpr int MOD = 1e9 + 7;
 
struct safe_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
void solve()
{
    int n, m; cin >> n >> m;
 
    int sx, sy; cin >> sx >> sy;
    int dx, dy; cin >> dx >> dy;
    --sx; --sy; --dx; --dy;
    
    vector<vector<char>> v(n, vector<char>(m));
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> v[i][j];
        }
    }
 
    deque<pair<pair<int, int>, int>> q;
    q.push_back({{sx, sy}, 0});
 
    while (!q.empty()) {
        pair<int, int> pos = q.front().first;
        int weight = q.front().second;
 
        if (pos.first == dx && pos.second == dy) {
            cout << weight << NL;
            return;
        }
 
        q.pop_front();
 
        visited[pos.first][pos.second] = true;
 
        for (int i = -2; i <= 2; ++i) {
            for (int j = -2; j <= 2; ++j) {
                int nx = pos.first + i;
                int ny = pos.second + j;
 
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] || v[nx][ny] == '#') continue;

                if (abs(i) + abs(j) != 1) {
                    q.push_back({{nx, ny}, weight + 1});
                } else {
                    q.push_front({{nx, ny}, weight});
                }
            }
        }
    }
 
    cout << -1 << NL;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 9756
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define inf 1000000000
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
bool comp(pair<pair<string,int>,int> a,pair<pair<string,int>,int> b){
if(a.first.first!=b.first.first)
    return (a.first.first<b.first.first);
else return (a.first.second>b.first.second);
}
int main(){
IOS;
int n;
cin>>n;
vector<pair<pair<string,int>,int> > v;
for(int i=0;i<n;i++){
    string s;
    int x;
    cin>>s;
    cin>>x;
    v.pb(mp(mp(s,x),i+1));
}
sort(v.begin(),v.end(),comp);
for(int i=0;i<n;i++){
    cout<<v[i].second<<endl;
}
}


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

using namespace std;

ifstream fin ("margele.in");
ofstream fout ("margele.out");

int n;

struct restaurant {
  string s;
  int p, i;
  bool operator < (const restaurant &rhs) {
    if (rhs.s == s)
      return p > rhs.p;
    else
      return s < rhs.s;
  }
};
restaurant v[102];

int main()
{
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].s >> v[i].p;
    v[i].i = i;
  }
  sort(v + 1, v + n + 1);
  for (int i = 1; i <= n; i++)
    cout << v[i].i << "\n";
  return 0;
}


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

vector<int> e[200010];
int s[200010], ns[2];

void dfs(int x, int p, int d) {
	s[x] = d;
	ns[d]++;
	for (auto y : e[x]) if (y != p) dfs(y,x,1-d);
}

int main() {
	ios::sync_with_stdio(false);
	int n; cin >> n;
	for (int i = 1; i < n; i++) {
		int a,b; cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,0,0);
	int n0 = n/3, n1 = n/3+((n%3)>0), n2 = n-n1-n0;
	for (int j = 0; j < 2; j++) if (ns[j] <= n0) {
		for (int i = 1; i <= n; i++) {
			if (s[i] == j) { cout << n0*3 << " "; n0--; }
			else {
				if (n1) { cout << n1*3-2 << " "; n1--; }
				else if (n2) { cout << n2*3-1 << " "; n2--;	}
				else { cout << n0*3 << " "; n0--; }
			}
		}
		cout << "\n";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (s[i] == 0) {
			if (n1) { cout << n1*3-2 << " "; n1--; }
			else { cout << n0*3 << " "; n0--; }
		}
		else {
			if (n2) { cout << n2*3-1 << " "; n2--; }
			else { cout << n0*3 << " "; n0--; }
		}
	}
	cout << "\n";
}

Measured memory_bytes: 18432
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    string s; cin>>s;

    REP(S,1<<3){
        int result=s[0]-'0';
        string ans; ans+=s[0];

        REP(i,3){
            if(S>>i&1){
                result+=s[i+1]-'0';
                ans+='+';
                ans+=s[i+1];
            }
            else{
                result-=s[i+1]-'0';
                ans+='-';
                ans+=s[i+1];
            }
        }
        if(result==7){
            ans+="=7";
            cout<<ans<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int infI=1e9+5;
const long long infL=1e16;
const int MOD=1e9+7;
const int MAX=2e5+5;

#define mp make_pair
#define in &
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define pll pair<ll,ll>
#define vvl vector<vector<ll> >
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define eb emplace_back
#define forn(i,a,b) for(ll i=a;i<b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define popb pop_back()
#define se second
#define fi first
#define test(t) int t;cin>>t;while(t--)
#define debug(x) cerr<<"=>"<<#x<<" = "<<x<<endl

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    if(b==1){
        return a;
    }
    ll temp=power(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2){
        temp=(temp*a)%MOD;
    }
    return temp;
}

//only use if mod is prime
ll mod_inv(ll a,ll mod){
    a%=mod;
    return power(a,mod-2);
}

void extended_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    ll x1,y1;
    extended_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return;
}

//TLE can also occur if vectors are not passed by reference
//priority_queue implements max heap by default

int main(){
    fastio;
    int n;
    ll k;
    cin>>n>>k;
    vl a(n);
    forn(i,0,n){
        cin>>a[i];
    }
    vl b = a;
    sort(b.begin(),b.end());
    ll ans = 0;
    forn(i,0,n){
        ll temp = lower_bound(b.begin(),b.end(),a[i])-b.begin();
        ll u = (((k*(k-1))%MOD)*temp)%MOD;
        u = (u*mod_inv(2,MOD))%MOD;
        ans = (ans+u)%MOD;
    }
    forn(i,0,n){
        forn(j,i+1,n){
            if(a[i]>a[j]){
                ans = (ans + k)%MOD;
            }
        }
    }
    cout<<ans;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

int main() {
    ll N;
    cin >> N;
    cout << N * (N - 1) / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int N, i;

int main(void){
    
    scanf("%d %d", &N, &i);
    printf("%d\n", N + 1 - i);
    
    
    return 0;
}


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

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

    vector<int> f(M);

    for (int i=0;i<N;++i) {
        int K;
        cin >> K;
        for (int j=0;j<K;++j) {
            int A;
            cin >> A;
            f[A-1]++;
        }
    }

    cout << count_if(f.begin(), f.end(), [N](int ff){ return ff == N;}) << endl;

    return 0;
}

Measured memory_bytes: 256
def getval():
    n = int(input())
    h = list(map(int,input().split()))
    return n,h 

def main(n,h):
    dp = [0,abs(h[1]-h[0])]
    for i in range(1,n-1):
        x = dp[-1]+abs(h[i+1]-h[i])
        y = dp[-2]+abs(h[i+1]-h[i-1])
        dp.append(min(x,y))
    print(dp[-1])
        
if __name__=="__main__":
    n,h = getval()
    main(n,h)

Measured memory_bytes: 89944
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	int encode(String... s) {
		int res = 0;

		res += Integer.parseInt(s[0])*60*60;
		res += Integer.parseInt(s[1])*60;
		res += Integer.parseInt(s[2]);

		return res;
	}

	void run() {
		MyScanner sc = new MyScanner();

		int[] a = new int[100000];
		while (true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}
			Arrays.fill(a, 0);
			for (int i = 0; i < n; i++) {
				int s = encode(sc.next().split(":"));
				int t = encode(sc.next().split(":"));
				a[s]++;
				a[t]--;
			}

			int max = 0, sum = 0;
			for (int i = 0; i < 100000; i++) {
				sum += a[i];
				max = Math.max(max, sum);
			}
			
			System.out.println(max);
		}
	}

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

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}
		System.out.println("----------------------------" + '\n');
	}

	class MyScanner {
		int read() {
			try {
				return System.in.read();
			} catch (IOException e) {
				throw new InputMismatchException();
			}
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

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

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

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

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

Measured memory_bytes: 98252