akhauriyash/Code-Regression huggingface dataset:
// 修改自提交记录：232713
// 原记录作者：E.Space (UID: 1579)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
char map[111][111],tmp[111];
int sr[111][111];
int sc[111][111];
int f[111][111];
int main()
{
	int n=io::F(),m=io::F();
	for(register int i=1;i<=n;++i)
		scanf("%s",map[i]+1);
	int x,y;
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			if(map[i][j]=='E'){x=i,y=j;break;}
	if(x>n/2)
	{
		x=n+1-x;
		for(register int i=1,j=n;i<j;++i,--j)
			memcpy(tmp,map[i],sizeof(tmp)),
			memcpy(map[i],map[j],sizeof(tmp)),
			memcpy(map[j],tmp,sizeof(tmp));
	}
	if(y>m/2)
	{
		y=m+1-y;
		for(register int i=1;i<=n;++i)std::reverse(map[i]+1,map[i]+m+1);
	}
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			sr[i][j]=sr[i][j-1]+(map[i][j]=='o'),
			sc[i][j]=sc[i-1][j]+(map[i][j]=='o');
	int ans=0;
	for(register int i=1;i<=x;++i)
		for(register int j=1;j<=y;++j)
		{
			int d=i+n-x-x+1,r=j+m-y-y+1;
			for(register int k=i;k<=d;++k)
				for(register int l=j;l<=r;++l)
					f[k][l]=0;
			for(register int k=i;k<i+x;++k)
				f[i][j]+=sr[k][j+y-1]-sr[k][j-1];
			for(register int k=i;k<=d;++k)
				for(register int l=j;l<=r;++l)
				{
					int t=f[k][l]+sc[k+x-1][l+y]-sc[k-1][l+y];
					cmax(f[k][l+1],t);
					t=f[k][l]+sr[k+x][l+y-1]-sr[k+x][l-1];
					cmax(f[k+1][l],t);
				}
			cmax(ans,f[d][r]);
		}
	printf("%d\n",ans);
	return 0;
}

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

int main()
{
    char str[4];
    int ans = 0;

    cin >> str;

    for (int i = 0; i < 4; i++) {
        if (str[i] == '+')
            ans++;
        else 
            ans--;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
op = {'N':(1,5,2,3,0,4), 'S':(4,0,2,3,5,1), 'E':(3,1,0,5,4,2), 'W':(2,1,5,0,4,3)}
f = input().split()
for i in input():
    f = [f[j] for j in op[i]]
print(f[0])

Measured memory_bytes: 7508
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

struct node {
    int id, val;
}stu[100010];

inline int cmp(const node& a, const node& b) {return a.val < b.val;}
int main() {
    int n; 
    cin >> n;
    for (int i = 1; i <= n; ++i) scanf("%d", &stu[i].val), stu[i].id = i;
    sort(stu + 1, stu + n + 1, cmp);
    for (int i = 1; i < n; ++i) printf("%d ", stu[i].id);
    printf("%d\n", stu[n].id);
    // system("pause");
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	string s, t, u;
	cin >> s >> t;
	int a, b;
	cin >> a >> b >> u;
	if (s == u) { --a; }
	if (t == u) { --b; }
	cout << a << " " << b << endl;

	return 0;
}


Measured memory_bytes: 256
def main():

#---------------------------------------------------------

    N = int(input())
    ans = 0
    for i in range(1, N + 1):
        n = N // i  # 項数n
        cnt = (n * (2 * i + (n - 1) * i)) // 2  # 初項i, 項数n の等差数列の和の公式
        ans += cnt
    print(ans)

#---------------------------------------------------------

if __name__ == '__main__':
   main()

Measured memory_bytes: 63064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a7=1000000007;
ll inf=100000000000000000;

int main()
{
  ll n;string s;cin>>n>>s;
  if(n%2!=0){
    cout<<"No";
  }
  else{
    string t[2];
    t[0]="";t[1]="";
    for(ll i=0;i<n;i++){
      if(i<n/2)t[0]+=s[i];
      else t[1]+=s[i];
    }
    if(t[0]==t[1])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
def resolve():
    A, B = map(int, input().split())
    ans = 0
    for i in range(1, A+1):
        for j in range(10, B+1):
            if str(j)[0] != "1" and str(j)[1] != "1":
                if int(str(j)[0])*int(str(j)[1]) == i:
                    ans += 1
    print(ans)
resolve()

Measured memory_bytes: 9192
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = (int)1e5 + 10;
string s;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> s;
    for (int i = 0; i < 26; i++) {
        pair < int, int > mn = make_pair(1e9, 0);
        int cur = 0;
        int prv_bal = 0;
        for (int j = 0; j < s.size(); j++) {
            prv_bal = cur;
            if (s[j] == i + 'a') cur++;
            else cur--;
            if (cur > mn.first) {
                cout << mn.second + 1 << " " << j + 1 << '\n';
                exit(0);
            }
            mn = min(mn, make_pair(prv_bal, j));
        }
    }
    cout << -1 << " " << -1;
    return 0;
}

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

using namespace std;

int main(){
  string s;
  cin >> s;
  string a = "";
  for(int i = 0; i < s.length(); i++){
    if (i%2 == 0){
      a += s.at(i);
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    string s; cin >> s;
    int n = s.size();
    map<char,int> mp;
    mp['a'] = mp['b'] = mp['c'] = 0;
    rep(i,n) mp[s[i]]++;
    int mn = inf;
    for (auto x : mp) mn = min(mn,x.second);
    for (auto x : mp) mp[x.first] -= mn;
    if (mp['a'] <= 1 && mp['b'] <= 1 && mp['c'] <= 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 3748
<?php
    list($A,$B,$H,$M) = array_map('intval',explode(" ",(trim(fgets(STDIN)))));
    
    //H時M分の時の針の角度を求めたいので0時0分を共に0度として計算する。
    $angle_a = 360/12 * $H + 30/60 * $M;
    $angle_b = 360/60 * $M;
    
    $diff =  abs($angle_b-$angle_a);
    
    if($diff>180){
        $diff = 360 - $diff;
    }
    // echo $diff." ".$A." ".$B."\n";
    $C = sqrt($A**2 + $B**2 - 2*$A*$B*cos(deg2rad($diff)));
    
    echo $C."\n";
?>

Measured memory_bytes: 16480
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=51;
int n;
bool A[M][M];
vl a,b;
vvl dp(M,vl(M,INF));

int main(){
	cin>>n;
	a=b=vl(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		A[i][a[i]]=1;
	}
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<M;i++) dp[i][i]=0;
	for(ll i=1;i<M;i++) for(int j=0;j<M;j++) for(int k=0;k<M;k++) dp[j][k]=min(dp[j][k],dp[j%i][k]+(1ll<<i));
	for(int i=0;i<n;i++) if(dp[a[i]][b[i]]==INF){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<M;i++) for(int j=0;j<M;j++){
		ll t=0;
		while(dp[i][j]>1) dp[i][j]/=2,t++;
		dp[i][j]=t;
	}
	ll res=0;
	vl c(n);
	for(int i=0;i<n;i++) c[i]=dp[a[i]][b[i]];
	for(ll i=M-1;i>0;i--) for(int j=0;j<n;j++) if(c[j]==i){
		res+=1ll<<i;
		for(int k=0;k<n;k++){
			ll m=inf;
			for(int l=0;l<M;l++) A[k][l%i]|=A[k][l];
			for(int l=0;l<M;l++) if(A[k][l]) m=min(m,dp[l][b[k]]);
			c[k]=m;
		}
		break;
	}
	cout<<res<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<int,string> P;

int main(){
    int n,num;
    string str;
    map<P,int> m;
    
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> str >> num;
        m[P(str.size(),str)] += num;
    }
    
    map<P,int>::iterator it;
    for(it = m.begin() ; it != m.end() ; it++){
        cout << it->first.second << ' ' << it->second << endl;
    }

    return 0;
}

Measured memory_bytes: 1224
using System;
using System.Collections.Generic;

class Program{
  static void Main(){
    string S = Console.ReadLine();
    long K = long.Parse(Console.ReadLine());
    
    var l = new List<long>();
    long cnt = 1;
    string form = S.Substring(0, 1);
    for (int i = 1; i < S.Length; i++){
      string next = S.Substring(i, 1);
      if (next == form)
        cnt++;
      else{
        l.Add(cnt);
        cnt = 1;
        form = next;
      }
    }
    l.Add(cnt);
    
    long ans = 0;
    if (l.Count == 1){
      ans = (S.Length * K) / 2;
    }
    else if(S.Substring(0, 1) == S.Substring(S.Length - 1, 1)){
      long start = l[0];
      long end = l[l.Count - 1];
      long mid = 0;
      for (int j = 1; j < l.Count-1; j++)
        mid += l[j] / 2;
      long connect = (start + end) / 2;
      ans = (start/2) + mid*K + connect*(K-1) + (end/2);
    }
    else
    {
      long loop = 0;
      for (int j = 0; j < l.Count; j++)
        loop += l[j] / 2;
      ans = loop*K;
    }
    
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 11220
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
// #define mp make_pair
// #define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)
#define show(x) cout << #x << " = " << x << endl;

int memo[301];

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

}


int main(){
  ll n, m;
  cin >> n >> m;
  ll tmpa, tmpb;
  set<ll> sta, stb;
  REP(i,m){
    cin >> tmpa >> tmpb;
    if(tmpa == 1){
      sta.insert(tmpb);
    }
    if(tmpb == n){
      stb.insert(tmpa);
    }
  }
  for(auto itr =stb.begin(); itr != stb.end(); itr++){
    if(sta.find(*itr)!=sta.end()){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 9600
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val aList: List<Int> = readLine()!!.split(" ").map(String::toInt)
    val sum : Int = aList.sum()
    val th: Double = sum * (1 / (4 * m.toDouble()))
    var cnt: Int = 0
    for(i in 0..n-1) {
        if(aList[i] >= th) cnt += 1
        if(cnt == m) {
            println("Yes")
            return
        }
    }
    println("No")
}

Measured memory_bytes: 36340
import java.util.*;
public class Main { 
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       String o="";
       int a=sc.nextInt(); 
       if(a<=3){
         o=Integer.toString(a);
       }else{
      	while(a<=100003){
         int n=(int)Math.sqrt((double)a); 
         boolean end=false;
         for (int i=2;i<=n;i++){
              if(a%i==0){
                  break;
              }else if(i==n){
                  o=Integer.toString(a);
                	end=true;
                  break;
              }
            }
          if (end)break;
      	  a++;
    	}
       }
      System.out.println(o);
    }
}

Measured memory_bytes: 23252
#include<stdio.h>
int main()
{
    int a,b,c,r,d;
    scanf("%d%d%d",&a,&b,&c);
    d=a-b;
    if(d>=c)
     printf(" 0\n");
    else
    {
      r=c-d;
    printf("%d",r);
    }

    return 0;
}


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

using namespace std;

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

    int left = 0, right = 0, minv = 0;
    for (int i = 1; i < n; ++i) if (s[i] == 'E') right++;

    minv = right;

    for (int i = 1; i < n; ++i) {
        if (s[i] == 'E') right--;
        if (s[i - 1] == 'W') left++;
        minv = min(left + right, minv);
    }

    cout << minv << endl;

    return 0;
}

Measured memory_bytes: 900
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a;
	cin>>a;
	int b=a/1000,c=(a%1000)/100,d=(a%100)/10,e=a%10;
	if(b==c&&c==d){
	    cout<<"Yes"<<endl;
	}
	else{
	    if(c==d&&d==e){
	        cout<<"Yes"<<endl;
	    }
	    else{
	        cout<<"No"<<endl;
	    }
	}
}



Measured memory_bytes: 256
n = gets.chomp.to_i

d = Math.log10(n).floor + 1

# p d

if d == 1
  puts n
elsif d % 2 == 0
  puts '90' * (d / 2 - 1) + '9'
else
  c =  ('90' * ((d - 1) / 2 - 1) + '9').to_i
  puts c + (n - (('1' + ('0' * (d - 1))).to_i - 1))
end


Measured memory_bytes: 1788
#include <bits/stdc++.h> 
#define int long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bn begin()
#define en end()
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define vi vector<int>
#define qi queue<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
#define mod 1000000007LL
#define pi 3.141592653589
using namespace std;

int power(int x, int y) ;
int gcd(int a, int b) ;

signed main() {
    quickie
    int a, v, b, w, t ;
    cin >> a >> v >> b >> w >> t ;
    if(a < b) {
        if(v <= w) cout << "NO\n" ;
        else {
            int ans = b-a ;
            if(ans <= (v-w)*t) cout << "YES\n" ;
            else cout << "NO\n" ;
        }
    }
    else {
        if(v <= w) cout << "NO\n" ;
        else {
            int ans = a-b ;
            if(ans <= (v-w)*t) cout << "YES\n" ;
            else cout << "NO\n" ;
        }
    }
}

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

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


Measured memory_bytes: 3640
#include <algorithm>
#include <iostream>
#include <iterator>

int solve(int p, int q, int r)
{
  int a[] = {p, q, r};
  std::sort(std::begin(a), std::end(a));
  return a[0] + a[1];
}

int main()
{
  int p, q, r;
  std::cin >> p >> q >> r;

  std::cout << solve(p, q, r) << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    int r;
    cin >> r;
    cout << r*r << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	bool f[4] = {};
	char c;
	for (int i = 0; i < n; i++) {
		cin >> c;

		switch (c) {
		case 'P':
			f[0] = true;
			break;
		case 'W':
			f[1] = true;
			break;
		case 'G':
			f[2] = true;
			break;
		case 'Y':
			f[3] = true;
			break;
		}
	}

	int num = 0;
	for (int i = 0; i < 4; i++) {
		if (f[i]) {
			num++;
		}
	}

	if (num == 3) {
		cout << "Three" << endl;
	}
	else {
		cout << "Four" << endl;
	}

	return 0;
}

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

int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans1= max(a*c,a*d);
    ll ans2= max(b*c,b*d);
    ll ans= max(ans1,ans2);
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
#define lgx cerr << "-----------" << endl;

int main() {
	int x, y, z;
	while(cin >> x >> y >> z) {
		x -= z;
		int ans = x / (y+z);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

class Program
{
	//Main
	static void Main(string[] args)
	{
		//読み込む
		string[] S = Console.ReadLine().Split(' ');
		int N = int.Parse(S[0]);
		int M = int.Parse(S[1]);

		//union find木
		UnionFind groupTree = new UnionFind(N);

		//読み込む
		for(int i=0; i<M; i++){
				string[] line = Console.ReadLine().Split(' ');
				int A = int.Parse(line[0])-1;
				int B = int.Parse(line[1])-1;

				//UnionFindに組み込む
				groupTree.Merge(A,B);
		}


		//特定のグループの人数を格納
		/*
		根っことして有り得るのは0 ~ Nのどれか
		*/
		int[] groupNum = new int[N];

		for(int i=0; i<N; i++){
			//根っこを取得
			int root = groupTree.Root(i);
			//debug
			//Console.WriteLine("i={0}, root={1}",i,root);
			
			groupNum[root] ++;
		}

		//結局、一番人数の多いグループの構成員と同じだけに分ける必要
		int ans = groupNum.Max();
		Console.WriteLine(ans);
	}
}



//自作クラス
//ジェネリック（タイプを指定可能）ではなく、取り敢えずintに限定して作成
class UnionFind
{
		public readonly int[] Array;

		public UnionFind(int capacity)
		{
				this.Array = new int[capacity];

				//自身を根として初期化
				for(int i=0; i<capacity; i++){
						this.Array[i] = i;
				}
		}

		//unionFindへの追加（インデックスaとインデックスbの根を同一にする）
		public void Merge(int a, int b){
			//根を決定
			int rootA = Root(a);
			int rootB = Root(b);
			int newRoot = Math.Min(rootA, rootB);

			//より小さい方に根を変化させる
			this.Array[rootA] = newRoot;
			this.Array[rootB] = newRoot;
		}

		//根を判定し、出力
		public int Root(int ind){
			int root = 0;

			if(this.Array[ind] == ind){
					root = ind;
			}else{
					root = Root(this.Array[ind]);
			}

			//根をその場で更新しつつ、出力もする（一種のメモ化再帰とも）
			return this.Array[ind] = root;
		}

		//2つのインデックスの根が同一なら、trueを返す
		public bool SameRoot(int a, int b){
			return this.Root(a) == this.Root(b);
		}
}



Measured memory_bytes: 23896
#include <stdio.h>

int main(){
	int i,j,nedan,maisuu,kouka[6] = {500,100,50,10,5,1};
	for(i = 0;;i++){
		scanf("%d",&nedan);
		if(nedan == 0) return 0;
		nedan = 1000 - nedan;
		maisuu = 0;
		for(j = 0;j < 6;j++){
			maisuu += (nedan - (nedan % kouka[j])) / kouka[j];
			nedan = nedan % kouka[j];
		}
		printf("%d\n",maisuu);
	}
	return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

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

	/* 入力 */
	int n = scan.nextInt();
	int k = scan.nextInt();

	long ans = k*(long)Math.pow(k-1, n-1);

	/* 出力 */
	System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define p(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
//#define int long long


using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };




ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

ll pow2(ll a, ll n) {//aのn乗を計算します。
	ll x = 1;
	while (n > 0) {//全てのbitが捨てられるまで。
		if (n & 1) {//1番右のbitが1のとき。
			x = x * a;
		}
		a = a * a;
		n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
	}
	return x;
}

long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}


const int MOD = 1000000007;

bool arr[1050000];
int sosuu[100010];
void Eratosthenes() {
	ll N = 1050000;
	int c = 0;
	for (int i = 0; i < N; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < sqrt(N); i++) {
		if (arr[i]) {
			for (int j = 0; i * (j + 2) < N; j++) {
				arr[i *(j + 2)] = 0;
			}
		}
	}

	for (int i = 2; i < N; i++) {
		if (arr[i]) {
			sosuu[c] = i;
			//cout << sosuu[c] << " ";
			c++;
		}
	}
	//cout << endl;
	//cout << c << endl;
}


int a[100010];
int main() {
	int N; cin >> N;
	REP(i, N)cin >> a[i];
	int grad = 0;
	int cnt = 1;
	REP(i, N-1) {
		int d = a[i + 1] - a[i];
		if (grad == 0) {
			if(d>0){
				grad = 1;
			}
			if (d < 0)grad = -1;
		}
		else if (grad > 0) {
			if (d < 0) {
				cnt++; grad = 0;
			}
		}
		else {
			if (d > 0) {
				cnt++;
				grad = 0;
			}
		}
	}
	cout << cnt << endl;
}

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

#define REP(i,n) for(ll i=0; i<ll(n); i++)
#define FOR(i,m,n) for(ll i=ll(m); i<ll(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
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 int  INF = (1 << 30) - 1;
const ll INFL = 1LL << 60;
const ll mod = 10000000007;




int main() {

	int n, k;
	cin >> n >> k;

	VI a(n);
	REP(i, n)cin >> a[i];

	FOR(i, k , n) {
		if (a[i] > a[i - k])cout << "Yes" << endl;
		else cout << "No" << endl;
	}


}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define log(x,b) (log(b)/log(x))
#define rep(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int mod=1e9+7;

int32_t main()
{
    int w,a,b;
    cin>>w>>a>>b;
    if(b<a)swap(a,b);
    if(a<=b && b<=a+w)cout<<0<<endl;
    else {
        cout<<b-(a+w)<<endl;
    }

    return 0;
}


Measured memory_bytes: 3608
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//


int main() {

    ll K; cin >> K;
    ll n = 0;
    ll q = 1;
    int ans = -1;
    for (int i = 1; i <= K; ++i) {
        q %= K;
        n += 7 * q;
        n %= K;
        if (n == 0) {
            ans = i;
            break;
        }
        q *= 10;
    }

    cout << ans << endl;



    return 0;
}





Measured memory_bytes: 3612
#include <iostream>

using namespace std;

typedef long long llong;
llong dp[101][21];
// dp[今の項数][今の和の数]
// 初期化できるし関数使うからグローバル
llong nums[101];
// 送るのなんか面倒い
int n;

llong solve_dp(void){

  dp[0][nums[0]] = 1;
  // nums[0] になるのは必ず１通り

  for( int j = 0 ; j < n - 1 ; j++ ){
    for( int i = 0 ; i < 21 ; i++ ){
      if( i + nums[j + 1] <= 20 )
	dp[j + 1][i + nums[j + 1]] += dp[j][i];
      if( i - nums[j + 1] >= 0 )
	dp[j + 1][i - nums[j + 1]] += dp[j][i];
    } 
  }
  return dp[n - 2][nums[n - 1]];
}

int main(void){

  cin >> n;
  for( int i = 0 ; i < n ; i++ )
    cin >> nums[i];

  cout << solve_dp() << endl;

  return 0;
}

Measured memory_bytes: 1180
def dif(n,ab):
    c=[[sum(i),i] for i in ab]
    c.sort(reverse=True)

    ap=0
    bp=0
    for i in range(n):
        if i%2==0:
            ap+=c[i][1][0]
        else:
            bp+=c[i][1][1]


    return ap-bp

n=int(input())
print(dif(n,[list(map(int,input().split())) for i in range(n)]))

Measured memory_bytes: 38168
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
const long long MOD = 1e9+7;
bool ok(int now,int n,int m,int s[],int c[]){
    string ss = to_string(now);
    if(ss.size()!=n) return false;
    rep(i,m) if((ss[s[i]-1]-'0')!=c[i]) return false;
    return true;
}
int main(){
    int n,m;
    cin >> n >> m;
    int now = pow(10,n-1);
    if(n==1) now = 0;
    int s[m],c[m];
    rep(i,m) cin >> s[i] >> c[i];
    while(!ok(now,n,m,s,c)){
        now++;
        if(now==1023) break;
    }
    if(now!=1023) cout << now << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include<vector>
#include<tuple>

using namespace std;
int main(){
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;

  if(e-a<=k) cout << "Yay!";
  else cout << ":(";
}


Measured memory_bytes: 256
def inpl(): return list(map(int, input().split()))

S = input()
N = len(S)

R = [0]*N
L = [0]*N


for i in range(N-2, -1, -1):
    r = int(S[i] == "R")
    R[i] = R[i+1]*r + r

for i in range(1, N):
    l = int(S[i] == "L")
    L[i] = L[i-1]*l + l

X = [0]*N
for i in range(N):
    if S[i] == "R":
        X[i+R[i]-R[i]%2] += 1
    else:
        X[i-L[i]+L[i]%2] += 1

print(*X)

Measured memory_bytes: 50236
K, N = map(int, input().split())

input_list = list(map(int, input().split()))

ans = -1
for i in range(len(input_list)-1):
  ans = max(ans, input_list[i+1] - input_list[i])

ans = max(ans, input_list[0] + K - input_list[-1])
print(K - ans)

Measured memory_bytes: 26420
#include<iostream>
using namespace std;
int main(){
  int n, h[100000];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  h[n]=1000000001;
  int cnt=0, ans=0;
  for(int i=0; i<n; i++){
    if(h[i]>=h[i+1]){
      cnt++;
    }else{
      if(ans<cnt){
        ans=cnt;
      }
      cnt=0;
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 640
// C - Snuke Festival

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int A[100000], B[100000], C[100000];

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

	for (int i=0; i<N; i++) {
		cin >> A[i];
	}

	for (int i=0; i<N; i++) {
		cin >> B[i];
	}

	for (int i=0; i<N; i++) {
		cin >> C[i];
	}

	sort(A, A+N);
	sort(C, C+N);

	ll ans = 0;
	for (int i=0; i<N; i++) {
		int max_A_idx = lower_bound(A, A+N, B[i]) - A - 1;
		ll A_count = max_A_idx + 1;
		int min_C_idx = upper_bound(C, C+N, B[i]) - C;
		ll C_count = N - min_C_idx;

		ans += A_count * C_count;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>

int main(){
	char S[4];
	int ym,my;
	int fnum,lnum;
	
	scanf("%s",&S);
	
	ym=1;
	my=1;
	
	fnum=(S[0]-'0')*10+(S[1]-'0');
	lnum=(S[2]-'0')*10+(S[3]-'0');
	
	if(fnum==0 || fnum>12)	my=0;
	if(lnum==0 || lnum>12)	ym=0;
	
	if(my==1 && ym==0)	printf("MMYY\n");
	if(my==0 && ym==1)	printf("YYMM\n");
	if(my==1 && ym==1)	printf("AMBIGUOUS\n");
	if(my==0 && ym==0)	printf("NA\n");
	
	return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] x1 = new int[N];
        int[] y1 = new int[N];
        int[] x2 = new int[N];
        int[] y2 = new int[N];
        TreeSet<Integer> set_x = new TreeSet<Integer>();
        TreeSet<Integer> set_y = new TreeSet<Integer>();
        for (int i=0;i<N;i++) {
            x1[i] = sc.nextInt();
            y1[i] = sc.nextInt();
            x2[i] = sc.nextInt();
            y2[i] = sc.nextInt();
            set_x.add(x1[i]);
            set_y.add(y1[i]);
            set_x.add(x2[i]);
            set_y.add(y2[i]);
        }
        ArrayList<Integer> list_x = new ArrayList<Integer>(set_x);
        ArrayList<Integer> list_y = new ArrayList<Integer>(set_y);

        int[] x1_new = new int[N];
        int[] y1_new = new int[N];
        int[] x2_new = new int[N];
        int[] y2_new = new int[N];
        for (int i=0;i<N;i++) {
            x1_new[i] = Collections.binarySearch(list_x, x1[i]);
            y1_new[i] = Collections.binarySearch(list_y, y1[i]);
            x2_new[i] = Collections.binarySearch(list_x, x2[i]);
            y2_new[i] = Collections.binarySearch(list_y, y2[i]);
        }

        int H = list_y.size();
        int W = list_x.size();
        int[][] map = new int[H][W];
        for (int i=0;i<N;i++) {
            map[y1_new[i]][x1_new[i]]++;
            map[y1_new[i]][x2_new[i]]--;
            map[y2_new[i]][x1_new[i]]--;
            map[y2_new[i]][x2_new[i]]++;
        }
        int[][] ruiseki = new int[H][W];
        for (int i=0;i<H-1;i++) {
            for (int j=0;j<W-1;j++) {
                ruiseki[i+1][j+1] = map[i][j]+ruiseki[i][j+1]+ruiseki[i+1][j]-ruiseki[i][j];
            }
        }
        long ans = 0L;
        for (int i=1;i<H;i++) {
            for (int j=1;j<W;j++) {
                if (ruiseki[i][j]>0) {
                    long area = (long)(list_x.get(j)-list_x.get(j-1))*(list_y.get(i)-list_y.get(i-1));
                    ans+=area;
                }
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 227068
# coding: utf-8
N, L = map(int, input().split())
A = list(map(int, input().split()))
# Lより小さい組み合わせしか無い場合おわり
flag = False
for i in range(N-1):
    if A[i] + A[i+1] >= L:
        importance_i = i
        flag = True
        break
if not flag:
    print("Impossible")
    exit()

l, r = 0, N-1
print("Possible")
ans = []
while r - l > 1:
    # print(l, r)
    if l < importance_i:
        ans.append(l+1)
        l += 1
    if r > importance_i+1:
        ans.append(r)
        r -= 1
# print("importance_i", importance_i)
ans.append(importance_i+1)
print(*ans, sep="\n")

Measured memory_bytes: 68708
#include <iostream>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}
int main(void) {
    ll A,B,C,D;cin>>A>>B>>C>>D;
    ll lc = lcm(C, D);
    // B以下でCでもDでも割り切れない整数の個数
    ll S_B = B - (B / C + B / D - B / lc);
    ll S_A_1 = A - 1 - ((A - 1) / C + (A - 1)/ D - (A - 1)/lc);

    cout << S_B - S_A_1 << endl;
    return 0;
}

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

using namespace std;

#define int long long

constexpr int INF = 1LL << 60;
constexpr double EPS = 1.0e-11;

typedef pair<int, int> pii;
typedef pair<int, pii> pipii;

constexpr int MAX_N = 200005;

int n, k, a[MAX_N], f[MAX_N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(16);

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

    sort(a, a + n, greater<>());
    sort(f, f + n);

    int l = 0, r = 1e13;
    while (0 < r - l)
    {
        auto mid = (l + r) / 2;

        int tmpK = k;
        bool ok = true;
        for (int i = 0; i < n; i++)
        {
            if (mid < (a[i] - tmpK) * f[i])
            {
                ok = false;
                break;
            }

            if (a[i] * f[i] <= mid) continue;
            tmpK -= ceil(a[i] - mid / (double) f[i]);
        }

        if (ok)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout << l << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    string a,b;
    int n,A=0,B=0;
    
    cin >> n ;
    
    for(int i=0;i<n;i++){
        cin >> a >> b ;
        
        if(a==b) {A++ ; B++ ;}
        else if (a>b) {A+=3 ;}
        else {B+=3 ;}
        
    }
    
    cout << A << " " << B <<endl;
    
}



Measured memory_bytes: 3164
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	static Scanner scanner;

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

	    int[] P=new int[3];
	    P[0]=gi();
	    P[1]=gi();
	    P[2]=gi();
	    Arrays.parallelSort(P);
//	    int a=gi();
//	    int p=gi();



	   
	    System.out.print(P[1]+P[0]);

//        if (a>12) {
//        	System.out.print(b);
//        }else if(a>5){
//        	System.out.print(b/2);
//        } else {
//        	System.out.print(0);
//        }


	}
	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35664
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define MP make_pair
#define pb push_back
#define int long long

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

static const int INF = INT_MAX;
static const LL L_INF = LLONG_MAX;
static const int MOD = (1000000000 + 7);

void init();
int Root( int x );
bool unite( int x, int y );
int getsize( int x );

int size[100005];
int root[100005];

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

    int n, m;
    cin >> n >> m;
    vector< P > v;
    init();

    for( int i = 0; i < m; ++i ) {
        int a, b;
        cin >> a >> b;
        v.pb( MP( a, b ) );
    }
    --n;
    int ans = n * ( n + 1 ) / 2;
    ++n;
    stack< int > st;
    for( int i = m - 1; i >= 0; --i ) {
        st.push( ans );
        int f_size = getsize( Root( v[i].F ) );
        int s_size = getsize( Root( v[i].S ) );
        bool flg = unite( v[i].F, v[i].S );
        if( flg ) ans -= f_size * s_size;
    }

    while( !st.empty() ) {
        cout << st.top() << endl; st.pop();
    }

    return 0;
}

void init() {

    for( int i = 0; i < 100005; ++i ) {
        root[i] = i;
        size[i] = 1;
    }
    return;
}

int Root( int x ) {
    if( root[x] == x ) return x;

    return root[x] = Root( root[x] );
}

bool unite( int x, int y ) {
    int rx = Root( x );
    int ry = Root( y );

    if( rx == ry ) return false;
    if( rx < ry ) {
        root[ry] = rx;
        size[rx] += size[ry];
    } else {
        root[rx] = ry;
        size[ry] += size[rx];
    }
    return true;
}

int getsize( int x ) {
    return size[x];
}



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

int main(){
   string s;
   cin >> s;
   if(s=="Sunny"){cout << "Cloudy" << endl;}
   else{
     if(s=="Cloudy"){cout << "Rainy" << endl;}
     else{cout << "Sunny" << endl;}
   }
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

num = [0]*100000

for i in range(N):
    num[A[i]-1] += 1

sum = sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    sum += (C[i]-B[i])*num[B[i]-1]
    num[C[i]-1] += num[B[i]-1] 
    num[B[i]-1] = 0

    print(sum)

Measured memory_bytes: 22164
n = int(input())

def drawKoch(p1, p2, i):
    if i == 0:
        print(*p1)
        return 0
    else:
        s = [p2[0]/3+p1[0]*2/3, p2[1]/3+p1[1]*2/3]
        t = [p2[0]*2/3+p1[0]/3, p2[1]*2/3+p1[1]/3]
        u = [p2[0]/2+p1[0]/2-(p2[1]-p1[1])/(2*(3**0.5)), \
            p2[1]/2+p1[1]/2+(p2[0]-p1[0])/(2*(3**0.5))]
        drawKoch(p1, s, i-1)
        drawKoch(s,  u, i-1)
        drawKoch(u,  t, i-1)
        drawKoch(t, p2, i-1)

p1_start = [0.0, 0.0]
p2_start = [100.0, 0.0]
drawKoch(p1_start, p2_start, n)
print(*p2_start)


Measured memory_bytes: 5716
// package cp;
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	long gcd(long a,long b) {if(b==0)return a;else return gcd(b,a%b);}
	void swap(long a,long b) {long temp=a;a=b;b=temp;}
	StringBuilder sb=new StringBuilder();
	BigInteger RES=new BigInteger("0");
	//(Initialize as string) - (a.add(b)) - (array initialized with null and not 0)
	Integer[] ARR=new Integer[5];
	//Integer sort-TLE-Initialize object elements i.e a[0].
	void divisor(long n,int start) {
		int cnt=0;for(int i=start;i<=Math.sqrt(n);i++) {
		if(n%i==0) {if(i==n/i)cnt++;else cnt+=2;}}}
	static long[][] dp;
	void f(int n,int j,long[][] a) {
		dp[n][j]=a[n][j]+Math.max(dp[n-1][(j+1)%3], dp[n-1][(j+2)%3]);
	}
	public static void main(String[] args) throws IOException {	
		PrintWriter out = new PrintWriter(System.out);
		Readers.init(System.in);
		//Cf_three obj=new Cf_three();
      	Main obj=new Main();
		int n=Readers.nextInt();
		long[][] a=new long[n][3];
		dp=new long[n][3];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				a[i][j]=Readers.nextLong();
				if(i==0)dp[i][j]=a[i][j];
			}
		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				obj.f(i, j,a);
			}
		}
//		System.out.println(Arrays.deepToString(dp));
		System.out.println(Math.max(dp[n-1][0], Math.max(dp[n-1][1], dp[n-1][2])));
		out.flush();
	}
}
class Readers {
 
    static BufferedReader reader;
 
    static StringTokenizer tokenizer;
 
 
 
    /** call this method to initialize reader for InputStream */
 
    static void init(InputStream input) {
 
        reader = new BufferedReader(
 
                     new InputStreamReader(input) );
 
        tokenizer = new StringTokenizer("");
 
    }
 
 
 
    /** get next word */
 
    static String next() throws IOException {
 
        while ( ! tokenizer.hasMoreTokens() ) {
 
            //TODO add check for eof if necessary
 
            tokenizer = new StringTokenizer(
 
                   reader.readLine() );
 
        }
 
        return tokenizer.nextToken();
 
    }
 
 
 
    static int nextInt() throws IOException {
 
        return Integer.parseInt( next() );
 
    }
 
	
 
    static double nextDouble() throws IOException {
 
        return Double.parseDouble( next() );
 
    }
    
    
    static long nextLong() throws IOException{
    	
		return Long.parseLong(next());
	}
 
}

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

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        string s = sc.Next();
        string s2 = s.Replace("x", "");
        if (s2 != string.Join("", s2.Reverse()))
        {
            Console.WriteLine(-1);
            return;
        }

        long answer = 0;

        int left = 0;
        int right = s.Length - 1;

        while (true)
        {
            if (s[left] == 'x' && s[right] == 'x')
            {
                left++;
                right--;
            }
            else if (s[left] == 'x')
            {
                answer++;
                left++;
            }
            else if (s[right] == 'x')
            {
                answer++;
                right--;
            }
            else
            {
                left++;
                right--;
            }
            if (left >= right)
            {
                break;
            }
        }

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 31420
A,B,C,D,E,F = map(int,input().split())

noudo = 0
ans = (100*A, 0)
for a in range(31):
    for b in range(31):
        water = A * a + B * b
        if water*100 > F:
            break
        for c in range(3001):
            water = A * a + B * b
            if water == 0:
                break
            can_sugar = water * E
            if C * c > can_sugar:
                break
            rest = F - water * 100 - C*c
            if rest < 0:
                break
            rest_sugar = can_sugar - C * c
            sugar = (min(rest_sugar, rest) // D) * D
            tmp = (sugar + C*c) / (water + sugar + C*c)
            if noudo < tmp:
                noudo = tmp
                ans = (water*100 + C*c + sugar, c*C + sugar)

print(ans[0], ans[1])




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

#define Bye return 0
#define ll long long

void solve(){
    int k, s; cin>>k>>s;
    int cont = 0;
    for (int x=0; x<=k; x++)
        for (int y=0; y<=k; y++){
            int z = s - x - y;
            cont += (z>=0 && z<=k);
        }

    cout<<cont<<endl;
}

int main(){
    solve();
    Bye;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int j = 0;
  cin >> N;
 
  // N要素の配列
  vector<int> A(N);
 
  // 入力処理
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  
  for (int i = 0; i < N; i++) {
    if( A.at(i) % 2 == 0){
      if( A.at(i) % 3 !=0 && A.at(i) % 5 != 0 ){
        j++;
      }
    }
  }
  if ( j == 0 ){
    cout << "APPROVED" << endl;
  }else{
    cout << "DENIED" << endl;
  }
}

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

const int N_MAX = 100010;
vector<vector<int>> T(N_MAX, vector<int>(0));
vector<bool> gone(N_MAX, false);
map<int, int> color;
map<P, ll> W;

void dfs(int n) {
  if (n == 0) {
    color[n] = 0;
    gone[n] = true;
  }
  for (auto t : T[n]) {
    if (gone[t]) {
      continue;
    }
    if (W[make_pair(n, t)]%2 == 0) {
      color[t] = color[n];
    }
    else if (color[n] == 0) {
      color[t] = 1;
    }
    else if (color[n] == 1) {
      color[t] = 0;
    }
    gone[t] = true;
    dfs(t);
  }
  return;
}

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N-1; i++) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    --u;
    --v;
    T[u].push_back(v);
    T[v].push_back(u);
    W[make_pair(u, v)] = w;
    W[make_pair(v, u)] = w;
  }
  dfs(0);
  for (auto c : color) {
    cout << c.second << endl;
  }
}

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

int main(){
	int s;
	cin >> s;
	int hour = s/3600;
	int minute = (s-3600*hour)/60;
	int second = (s-3600*hour-60*minute);

	cout << hour << ":" << minute << ":" << second << endl;
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>

using namespace std;

int a[1000000];

int main(){
	
	int num, L;
	
	while(true){
		cin >> num >> L;
		
		if(L == 0){
			break;
		}
		
		for(int i = 0; i < 1000000; i++){
			a[i] = 0;
		}
		
		a[num] = 1;
		
		int ans1, ans2, ans3;
		
		for(int i = 2; i < 100000000; i++){
			int b[6] = {};
			for(int j = 0; j < L; j++){
				b[j] = num % 10;
				num /= 10;
			}
			sort(b, b + L);
			int nex = 0;
			for(int j = 0; j < L; j++){
				nex *= 10;
				nex += (b[L - 1 - j] - b[j]);
			}
			//cout << nex << " ";
			if(a[nex] != 0){
				ans1 = a[nex] - 1;
				ans2 = nex;
				ans3 = i - ans1 - 1;
				break;
			}
			num = nex;
			a[num] = i;
		}
		cout << ans1 << " " << ans2 << " " << ans3 << endl;
	}
	
	return 0;
}

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


int main () {

    int n, q;
    int s[10000];
    int t[10000];
    int answer = 0 ;

    cin >> n;

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

    }

    for (int i = 0; i < q; i++ ) {
        for (int j = 0; j < n; j++ ) {
            if (s[j] == t[i]) {
                answer++;
                break;

            }
        }
    }

    cout << answer << endl;



    return 0;
}
 

Measured memory_bytes: 3092
#include <iostream>
using namespace std;
int b[10000000];
int main()
{
	int a;
	cin >> a;
	int c = a;
	for (int i = 0; i < a; i++) {
		cin >> b[i];
		if (i > 0)if (b[i] > b[i - 1]) {
			c -= 1;
		}
	}
	cout << c << endl<< a << endl;
}



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


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		char[] c = sc.next().toCharArray();

		if (c[0] == 'a' || c[0] == 'o' || c[0] == 'i' || c[0] == 'e' || c[0] == 'u') {
			pr.println("vowel");
		} else {
			pr.println("consonant");
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 9680