akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007
#define MP make_pair
#define PB push_back
typedef long long ll;

int N, a[40400], b[40400], p[20200];

int q (int* x, int i) {
        int res = 0;
        for (i += N; i; i /= 2) res += x[i];
        return res;
}

void u (int* x, int l, int r, int d) {
        for (l += N, r += N; l<r; l /= 2, r /= 2) {
                if (l&1) x[l++] += d;
                if (r&1) x[--r] += d;
        }
}

int main () {
        scanf("%d", &N);
        fo(i, 0, N) {
                u(a, i, i+1, i);
                u(b, i, i+1, N-i-1);
                scanf("%d", &p[i]), p[i]--;
        }
        fo(j, 0, N) {
                int i = p[j];
                u(b, i, i+1, j);
                if (i) {
                        int d = q(b, i) + 1 - q(b, i-1);
                        u(a, 0, i, -d);
                        u(b, 0, i, d);
                }
        }
        int mna = 2e9, mnb = 2e9;
        fo(i, 0, N) {
                mna = min(mna, q(a, i));
                mnb = min(mnb, q(b, i));
        }

        u(a, 0, N, 1-mna);
        u(b, 0, N, 1-mnb);

        fo(i, 0, N) printf("%d ", q(a, i)); puts("");
        fo(i, 0, N) printf("%d ", q(b, i));
        return 0;
}


Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;

namespace program
{
    class Program
    {
        static void Main()
        {
          int[] a = Input.ScanIntArray();
          Array.Sort(a);
          if(a[0]==1 && a[1]==4 && a[2]==7 &&a[3]==9)
            Console.WriteLine("YES");
          else
            Console.WriteLine("NO");
        }
    }

    static class Input
    {
        static public int ScanInt() { return int.Parse(Console.ReadLine()); }
        static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
        static public double ScanDouble() { return double.Parse(Console.ReadLine()); }
        static public long ScanLong() { return long.Parse(Console.ReadLine()); }
        static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
        static public int[] ScanIntArray() { return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray(); }
        static public uint[] ScanUintArray() { return Console.ReadLine().Split(' ').Select(x => uint.Parse(x)).ToArray(); }
        static public double[] ScanDoubleArray() { return Console.ReadLine().Split(' ').Select(x => double.Parse(x)).ToArray(); }
        static public long[] ScanLongArray() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray(); }
        static public ulong[] ScanUlongArray() { return Console.ReadLine().Split(' ').Select(x => ulong.Parse(x)).ToArray(); }

        static public string ScanStr() { return Console.ReadLine(); }
        static public string[] ScanStrArray() { return ScanStr().Split(' '); }
    }

    static class MyMath
    {
        public static int GCD(int a, int b)
        {
            Func<int, int, int> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static ulong GCD(ulong a, ulong b)
        {
            Func<ulong, ulong, ulong> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static int LCM(int a, int b)
        {
            return a * b / GCD(a, b);
        }
        public static ulong LCM(ulong a, ulong b)
        {
            return a * b / GCD(a, b);
        }
    }
}


Measured memory_bytes: 11348
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::iter;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::usize;

#[allow(unused_macros)]
macro_rules! read_cols {
    ($($t:ty),+) => {{
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();

        let mut it = line.trim()
            .split_whitespace();

        ($(
            it.next().unwrap().parse::<$t>().ok().unwrap()
        ),+)
    }}
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let costs: [usize; 10] = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6];

    let (n, m) = read_cols!(usize, usize);
    let mut a = read_vec::<i64>();

    assert_eq!(a.len(), m);

    a.sort();

    let mut dp = vec![None; 10001];
    dp[0] = Some(0usize);
    let dp = a.iter().fold(dp, |mut dp, &aa| {
        let cost = costs[aa as usize];
        for i in cost..dp.len() {
            let candidate = match dp[i - cost] {
                Some(ref prev) => prev + 1,
                None => {
                    continue;
                }
            };
            dp[i] = match dp[i] {
                Some(current) if candidate > current => Some(candidate),
                None => Some(candidate),
                _ => {
                    continue;
                }
            };
        }
        dp
    });

    let len = dp[n].unwrap();
    let ans = (0..len).fold((String::new(), n), |(s, current), _| {
        let (aa, next) = a.iter()
            .rev()
            .map(|&aa| (aa, costs[aa as usize]))
            .filter(|&(_, c)| c <= current)
            .filter_map(|(aa, c)| dp[current - c].map(|l| (aa, c, l)))
            .find(|&(_, _, l)| l == len - s.len() - 1)
            .map(|(aa, c, _)| (aa, current - c))
            .expect("found");
        (s + &aa.to_string(), next)
    }).0;
    println!("{}", ans);
}


Measured memory_bytes: 4352
/**
 * Created by hiramekun at 20:49 on 2019-11-09.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n;
    cin >> n;
    if (n % 2 == 0) cout << n / 2 - 1 << '\n';
    else cout << n / 2 << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;



int main() {

	int x;
	cin >> x;

	int f = x % 7;

	if (f == 1) cout << "fri" << endl;
	else if (f == 2)cout << "sat" << endl;
	else if (f == 3)cout << "sun" << endl;
	else if (f == 4)cout << "mon" << endl;
	else if (f == 5)cout << "tue" << endl;
	else if (f == 6)cout << "wed" << endl;
	else cout << "thu" << endl;

	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e, o;
vector<int> v, ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		if (x & 1) o.push_back(x);
		else e.push_back(x);
	}
	if (o.size() >= 3) {
		puts("Impossible");
		return 0;
	}
	if (o.size() == 0) {
		v = e;
	} else if (o.size() == 1) {
		v.push_back(o[0]);
		v.insert(v.end(), e.begin(), e.end());
	} else {
		v.push_back(o[0]);
		v.insert(v.end(), e.begin(), e.end());
		v.push_back(o[1]);
	}
	for (int i = 0; i < (int)v.size(); i++)
		printf("%d ", v[i]);
	puts("");
	if (v.size() == 1) {
		if (v[0] - 1) ans.push_back(v[0] - 1);
		ans.push_back(1);
	} else {
		if (v[0] - 1) ans.push_back(v[0] - 1);
		ans.push_back(2);
		for (int i = 1; i < (int)v.size() - 1; i++)
			ans.push_back(v[i]);
		if (v.back() - 1) ans.push_back(v.back() - 1);
	}
	printf("%d\n", (int)ans.size());
	for (int i = 0; i < (int)ans.size(); i++)
		printf("%d ", ans[i]);
	puts("");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;

string d = "dream";
string dr = "dreamer";
string e = "erase";
string er = "eraser";


 bool check(string s, ll r){
   if (r == 0) return true;

   if (r>=5 && s.substr(r-5,5)==d){
     return check(s, r-5);
   } else if (r>=7 && s.substr(r-7,7)==dr){
    return check(s, r-7);
  } else if (r>=5 && s.substr(r-5,5)==e){
     return check(s, r-5);
   } else if (r>=6 && s.substr(r-6,6)==er){
     return check(s, r-6);
   }

   return false;
 }

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

  string s;
  cin >> s;

  cout << ((check(s, s.length())) ? "YES" : "NO") << "\n";

  return 0;
}


Measured memory_bytes: 2384
#include<bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define M        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n,m;
    cin>>n>>m;
    
    string s[n];
    
    for(ll i=0; i<n; i++) cin>>s[i];
    
    bool g[n]={false}, h[m]={false};
    
    for(ll i=0; i<n; i++){
        for(ll j=0; j<m; j++){
            if(s[i][j]=='#'){
                g[i]=true; h[j]=true;
            }
        }
    }

    for(ll i=0; i<n; i++){
        if(g[i]) for(ll j=0; j<m; j++){
           if(h[j]) cout<<s[i][j];
        }
        if(g[i]) cout<<endl;
    }
    
    return 0;
}


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

int main()
{
    string s;
    cin >> s;
    auto n = s.size();
    long long res = 0;
    long long nA = 0;
    for(int i=0;i<n;i++){
        if(s[i]=='A'){ nA++; continue;}
        if(!(s[i]=='B' && s[i+1]=='C')){ nA=0; continue;}
        res += nA;
        i++;
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
signed main(){
  ll n,a=0,b;
  cin>>n;
  b = n;
  while(b>0){
    a += b % 10;
b /= 10;
  }
  if(n%a==0){
    cout<<"Yes\n";
  }else{
    cout<<"No\n";
  }
  return(0);
} 

Measured memory_bytes: 256
<?php
//error_reporting(0);
$N = trim(fgets(STDIN));
//$h = explode(" ",trim(fgets(STDIN)));
for($i=0;$i<$N;$i++) {
  list($A[],$B[]) = explode(" ",trim(fgets(STDIN)));
  $AB[]=$A[$i]+$B[$i];
}
arsort($AB);
$t=0;
$a=0;
for($i=0;$i<$N;$i++) {
  if ($i%2==0) {
    $t+=$A[key($AB)];
  }
  else {
    $a+=$B[key($AB)];
  }
  next($AB);
}
printf("%d\n",$t-$a);


Measured memory_bytes: 28272
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<n;++i)

typedef long long ll;
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    string s;
    cin >> s;
    map<char, int> m{};
    REP(i, s.length()){
        ++m[s[i]];
    }
    for(auto i=m.begin();i!=m.end();++i){
        if(i->second%2==1){
            cout << "No" << "\n";
            return 0;
        }
    }
    cout << "Yes" << "\n";
    return 0;
}

Measured memory_bytes: 256
S = input()
sample = "keyence"
flag = 0
num = 0
for i in range(7):
    if S[i] == sample[i]:
        num += 1
    else:
        break
if num == 7:
    print("YES")
elif sample[num:] == S[-(7 - num):]:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main(){
	int n;
	cin>>n;
	vector<int> d(n);
	rep(i,0,n) cin>>d[i];
	sort(all(d));
	vector<int> a;
	rep(i,0,4){
		rep(j,0,4){
			if(i==j) continue;
			int tmp=d[i]*pow(10,(int)log10(double(d[j]))+1)+d[j];
			//cout<<d[i]<<" "<<d[j]<<" "<<tmp<<endl;
			a.push_back(tmp);
		}
	}
	sort(all(a));
	cout<<a[2]<<endl;
}

Measured memory_bytes: 1332
#include<stdio.h>
#include<stdlib.h>

int main(void){
    int N,i,s=0,S=0;
    int *d;
    scanf("%d",&N);
    d = malloc(sizeof(int)*N);
    for(i=0;i<N;i++){
        scanf("%d",&d[i]);
        s += d[i];
    }
    for(i=0;i<N;i++){
        s -= d[i];
        S += s * d[i];
    }
    printf("%d",S);
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

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

	while (scan.hasNext()) {
	    int n = scan.nextInt();
	    int S = 0;

	    for (int i=0; i<600; i+=n) {
		int h = i * i;
		S += (n * h);
	    }
	    
	    System.out.println (S);

	}
    }
}

Measured memory_bytes: 26100
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, n) cin >> v[i];
  sort(v.begin(), v.end());
  double ans = v[0];
  rep(i, n-1){
    ans = (ans + (double)v[i+1]) / 2.0;
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3700
from collections import defaultdict


def factorize(N):  # 素因数分解
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())

fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
for vfact in fact.values():
    for i in cnt:
        cnt[i] += (vfact >= i)

ans = cnt[4] * (cnt[4] - 1) * (cnt[2] - 2) // 2
ans += cnt[24] * (cnt[2] - 1) + cnt[14] * (cnt[4] - 1) + cnt[74]
print(ans)


Measured memory_bytes: 65080
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,p;
    while(scanf("%d %d",&n,&p),n!=0) {
        int wan=p;
        int idx=0,stone[50]={0};
        while(1) {
            if(wan>0) {
                stone[idx]++;
                wan--;
                if(stone[idx]==p) break;
            }else {
                wan=stone[idx];
                stone[idx]=0;
            }
            idx=(idx+1)%n;
        }
        printf("%d\n",idx);
    }
}

Measured memory_bytes: 3104
n = int(input())
p = list(map(int, input().split()))

answer = 0
for i in range(n - 2):
    if p[i] < p[i + 1] < p[i + 2]:
        answer += 1
    if p[i] > p[i + 1] > p[i + 2]:
        answer += 1
print(answer)

Measured memory_bytes: 9172
class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0 for _ in range(t * 2 - 1)]

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = [1 << (ord(c) - ord('a')) for c in iterable]
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = 1 << (ord(value) - ord('a'))
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result | self._data[l]
            if r & 1 == 0:
                result = result | self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


N = int(input())
S = input()

st = SegmentTree(N)
st.update_all(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))


Measured memory_bytes: 48212
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>

#define REP(i,n) for(i=0; i < (n); i++)
#define REPONE(i, n) for(i=1; i <= (n); i++)
#define LOOP(n) for(int loopCount=1; loopCount <= (n); loopCount++)
#define ITER(c) __typeof((c).begin())
#define EACH(c,it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define SZ(c) ((int) (c).size())
#define ALL(c) c.begin(), c.end()
#define SUM(c) accumulate(ALL(c), 0)
#define EXIST(c,v) (find(ALL(c), (v)) != (c).end())
#define PB push_back
#define MP make_pair

using namespace std;
static const double EPS = 1e-9;
static const double PI = 3.141592653589793238462643383279;
typedef long long ll;

int main(){
    int i, j, n, cnt=1;
    double r, x, y;
    while(scanf("%d",&n)){
        if(!n) break;
        set<double> eventline;
        vector<double> xs, ys, rs;
        REP(i,n){
            scanf("%lf%lf%lf",&x,&y,&r);
            xs.PB(x);
            eventline.insert(x-r+EPS);
            eventline.insert(x+r+EPS);
            ys.PB(y);
            rs.PB(r);
        }
        double ans = 0.0, len = 0.0;
        EACH(eventline,it){
            vector< pair<double,double> > ranges;
            double lb = -(1<<20);
            REP(i,n){
                if(fabs((*it) - xs[i]) < rs[i])
                    ranges.PB(MP(ys[i] - rs[i], ys[i] + rs[i]));
            }
            len = 0;
            sort(ALL(ranges));
            REP(i,SZ(ranges)){
                len += max(0.0,ranges[i].second-max(lb,ranges[i].first));
                lb = max(lb, ranges[i].second);
            }
            if(len > EPS){
                ITER(eventline) itt = it; advance(itt,1);
                ans += len * ((*itt) - (*it));
            }
        }

        printf("%d %.2f\n",cnt++,ans);
    }
    return 0;
}

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

const int mn=1e6+7;
int vis[mn],n;

int main()
{
    scanf("%d",&n);
    if(n%2==0) {printf("-1");return 0;}
    if(n==1||n==7) {printf("1");return 0;}
    int t=7,cnt=1;t%=n;
    vis[t]=1;
    while(1) {
        t=(t*10+7)%n;
        cnt++;
        if(t==0) {printf("%d",cnt);return 0;}
        if(vis[t]) {printf("-1");return 0;}
        vis[t]=1;
    }
}

Measured memory_bytes: 7616
MOD=1000000007

N = int(input())
a = list(input())
b = list(input())

ans = 1
pre = 0
i=0
if a[i]!=b[i]:
    ans = 6
    i+=2
    pre = 2
else:
    ans = 3
    i+=1
    pre = 1

while i < N:
    if a[i]!=b[i]:
        if pre==1:
            ans = ans*2
            ans = ans%MOD
            i+=2
            pre = 2
        else:
            ans = ans*3
            ans = ans%MOD
            i+=2
            pre = 2
    else:
        ans = ans*(3-pre)
        ans = ans%MOD
        i+=1
        pre = 1

print(ans)

Measured memory_bytes: 61820
#include <bits/stdc++.h>
using namespace std;
long long dp[4][100001];//dp[i][j] iは最後に何を使ったか jは何日目か
int main(void){
	int N;
	cin >> N;
	int a[4][N+1];
	for(int i=1;i<=N;i++){
		cin >> a[1][i] >> a[2][i] >> a[3][i];
	}
	dp[1][1]=a[1][1];
	dp[2][1]=a[2][1];
	dp[3][1]=a[3][1];
	for(int i=2;i<=N;i++){
		for(int j=1;j<=3;j++){//a[j][i]を選んだ場合
			for(int k=1;k<=3;k++){//kは前日に選んだもの
				if(j==k)continue;//前日にjと同じ物を選んでいたら飛ばす
				long long temp = dp[k][i-1] + a[j][i];
				if( temp > dp[j][i])dp[j][i]=temp;
			}
		}
	}
	long long ans = dp[1][N];
	if(dp[2][N]>ans)ans=dp[2][N];
	if(dp[3][N]>ans)ans=dp[3][N];
	cout << ans;
	return 0;
}

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

from collections import Counter
N,M=map(int,input().split())
ufbs=UnionFind(N)
for _ in range(M):
    A,B=map(int,input().split())
    ufbs.union(A-1,B-1)
ans=0
for x in ufbs.roots():
    ans=max(ans,ufbs.size(x))
print(ans)


Measured memory_bytes: 88072
#include<stdio.h>

static int MAX = 500;
static int INFTY = (1<<21);

int main(){
  int n,i,j,k,sum;
  int M[MAX][MAX];
  int u,v;
  int min;
  int a[MAX];
  int b[MAX];
  int vis[MAX];

  scanf("%d", &n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&k);
      if(k==-1){
	M[i][j]=INFTY;
      }else{
	M[i][j]=k;
      }
    }
  }
  
  for(i=0;i<n;i++) {
    a[i]=INFTY;
    b[i]=-1;
    vis[i]=0;
    }
  
  a[0] = 0;
  
  while(1){
    min=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(min>a[i]&&!vis[i]){
	u=i;
	min=a[i];
      }
    }
    if(u==-1)break;
    vis[u]=1;
    for(v=0;v<n;v++){
      if(!vis[v]&&M[u][v]!=INFTY){
	if(a[v]>M[u][v]){
	  a[v]=M[u][v];
	  b[v]=u;
	}
      }
    }
  }
  
  sum=0;
  
  for(i=0;i<n;i++){
    if(b[i]!=-1)sum+=M[i][b[i]];
  }
    
  printf("%d\n",sum);
  
  return 0;
}



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

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

    set<string> S;

    rep(i,N) {
        string tmp;
        cin >> tmp;
        S.insert(tmp);
    }

    cout << S.size() << endl;


}

Measured memory_bytes: 19260
#include<iostream>
using namespace std;
int main(){
  int a,t[1000000],u[1000000];
  for(int i=0;i<1000000;i++){
    t[i]=1;
  }
  t[0]=t[1]=u[0]=u[1]=0;
  for(int i=2;i<=1000000;i++){
    if(t[i]==1){
      for(int j=i+i;j<1000000;j+=i)t[j]=0;
      u[i]=u[i-1]+1;
    }else{
      u[i]=u[i-1];
    }
  }
  while(cin>>a){
    cout<<u[a]<<endl;
  }
  return 0;
}


Measured memory_bytes: 10824
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
from itertools import permutations
for i,j in enumerate(permutations([i+1 for i in range(n)],n)):
  if p==list(j):a=i
  if q==list(j):b=i
print(abs(a-b))

Measured memory_bytes: 3060
#include<cstdio>
#include<algorithm>
using namespace std;
using ull = unsigned long long;

int main(){
	int N;
	scanf("%d", &N);
	unsigned A[N], B[N], C[N];
	for (int i = 0; i < N; ++i) scanf("%u", A + i);
	for (int i = 0; i < N; ++i) scanf("%u", B + i);
	for (int i = 0; i < N; ++i) scanf("%u", C + i);
	sort(A, A + N);
	sort(B, B + N);
	sort(C, C + N);
	ull answer = 0;
	for (int i = 0; i < N; ++i) answer += distance(A, lower_bound(A, A + N, B[i]))*distance(upper_bound(C, C + N, B[i]), C + N);
	printf("%llu\n", answer);
	return 0;
}

Measured memory_bytes: 1280
from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

print(ans)

Measured memory_bytes: 3188
fn main() {
    fn read<T: std::str::FromStr>() -> T {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        s.trim().parse().ok().unwrap()
    }
    fn read_vec<T: std::str::FromStr>() -> Vec<T> {
        read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
    }
    let ab = read_vec::<u64>();
    let a = ab[0];
    let b = ab[1];
    println!("{}", solve(a, b));
}

fn solve(a: u64, b: u64) -> u64 {
  f(a-1)^(f(b))
}
fn f(x: u64) -> u64{
  if x % 2 == 0 {
    x^(x/2%2)
  } else {
    f(x+1)^(x+1)
  }
}


Measured memory_bytes: 4352
#include<cstdio>

int main(void){
    int a, b;
    char op;

    while(1){
        scanf("%d %c %d", &a, &op, &b);
        if(op == '?') break;

        if(op == '+'){
            printf("%d\n", a + b);
        }else if(op == '-'){
            printf("%d\n", a - b);
        }else if(op == '/'){
            printf("%d\n", a / b);
        }else{
            printf("%d\n", a * b);
        }
    }

    return 0;
}

Measured memory_bytes: 1028
fun main(args: Array<String>) {
    val (N, M, L) = readLine()!!.split(" ").map {it.toLong()}

    val INF = 1e15.toLong()

    val d = Array(N.toInt() + 1) { i -> Array(N.toInt() + 1) { j -> if (i == j) 0 else INF } }

    for (i in 1..M) {
        val (A, B, C) = readLine()!!.split(" ").map {it.toLong()}
        if (C > L) {
            continue
        }
        d[A.toInt()][B.toInt()] = C
        d[B.toInt()][A.toInt()] = C
    }

    fun f(d: Array<Array<Long>>) {
        for (k in d.indices) {
            for (i in d.indices) {
                for (j in d.indices) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j])
                }
            }
        }
    }

    f(d)

    val d2 = Array(N.toInt() + 1) { i -> Array(N.toInt() + 1) { j -> when {
        i == j -> 0
        d[i][j] <= L -> 1
        else -> INF
    } } }

    f(d2)

    val Q = readLine()!!.toInt()

    for (i in 1 .. Q) {
        val (s, t) = readLine()!!.split(" ").map{it.toInt()}
        println(if (d2[s][t] == INF) -1 else d2[s][t] - 1)
    }
}


Measured memory_bytes: 131304
#include<stdio.h> 
#define MAXN 100005
#define NULL -1
typedef struct  {
	int p, l, r;
}Node;

Node T[MAXN];
int n, D[MAXN];

void print(int u)
{
	printf("node %d: ", u);
	printf("parent = %d, ", T[u].p);
	printf("depth = %d, ", D[u]);

	if (T[u].p == NULL)
		printf("root, ");
	else if (T[u].l == NULL)
		printf("leaf, ");
	else
		printf("internal node, ");

	printf("[");
	for (int i = 0, c = T[u].l; c != NULL; i++, c = T[c].r)
	{
		if (i)
			printf(", ");
		printf("%d", c);
	}
	printf("]\n");
}
int rec(int u, int p)
{
	D[u] = p;
	if (T[u].r != NULL)
		rec(T[u].r, p);
	if (T[u].l != NULL)
		rec(T[u].l, p + 1);
}
int main()
{
	int d, v, c, l, r;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		T[i].p = T[i].l = T[i].r = NULL;
	}

	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &v, &d);
		for (int j = 0; j < d; j++)
		{
			scanf("%d", &c);
			if (j == 0)
				T[v].l = c;
			else
				T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (T[i].p == NULL)
			r = i;
	}
	rec(r, 0);
	for (int i = 0; i < n; i++)
		print(i);
	return 0;
}



Measured memory_bytes: 6404
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i = (a);i < (n);i++)
typedef unsigned long long ull;
typedef long long ll;
using namespace std;

int main(){
    int a[5],memo = 0;
    
    rep(i,0,5){
        cin >> a[i];
        memo += max(a[i],40);
    }
    
    
    cout << memo/5 << endl;
    
    
    return 0;
}


Measured memory_bytes: 3136
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
multiset<int> s1;
vector<int> v1[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        if(l==0){
            s1.insert(r);
        }else{
            v1[l].push_back(r);
        }


    }
    for(int i=1;i<=m;i++){
        sort(v1[i].begin(),v1[i].end());
    }
    int ind = 0;
    for(int i=1;i<=m;i++){
        if(v1[i].size()>1){
            for(int j=0;j<v1[i].size()-1;j++){
                s1.insert(v1[i][j]);
            }
        }
        else if(v1[i].size()==0){
            if(s1.size()){
                if(*s1.begin()<=i){
                    s1.erase(s1.begin());
                }else{
                    ind = max(ind,i);
                    while(v1[ind].size()==0 && ind<=m){
                        ind++;
                    }
                    if(v1[ind].size()){
                        v1[ind].pop_back();
                    }
                }
            }else{
                ind = max(ind,i);
                    while(v1[ind].size()==0 && ind<=m){
                        ind++;
                    }
                    if(v1[ind].size()){
                        v1[ind].pop_back();
                    }
            }
        }
    }
    cout<<s1.size()<<endl;
}


Measured memory_bytes: 15232
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
  int w,h,x,y;
  std::cin >> w >> h >> x >> y;
  double half = (double)w*(double)h/2;
  int ans;
  if(2*x==w && 2*y==h) ans = 1;
  else ans = 0;
  print(half);
  print(ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
const int mod = (int)1e9 + 7;
const int inf = mod;
using namespace std;
#ifndef ONLINE_JUDGE
#define tr(...) {__l(__LINE__);__f(#__VA_ARGS__, __VA_ARGS__);}
inline void __l(int line) { cerr << "#" << line << ": "; }template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define tr(...)
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}
const int N = (int)1e4 + 10;
// make sure N size is correctttt!!!!!!!!!


int n, a[N], m;
vector<int> f;
int dp[15][N];

int solve(int idx, int coins){
   if(coins < 0)
      return -inf;

   if(idx == m){
      return dp[idx][coins] = ((coins == 0) ? 0 : -inf);
   }

   int &ans = dp[idx][coins];
   if(~ans)
      return ans;

   ans = -inf;
   if(f[a[idx]] <= coins){
      smax(ans, 1 + solve(idx, coins-f[a[idx]]));
   }

   smax(ans, solve(idx+1, coins));
   return ans;
}

void trace(int idx, int coins){
   if(idx == m){
      assert(coins == 0);
      exit(0);
   }

   if(f[a[idx]] <= coins){
      if(solve(idx, coins) == 1 + solve(idx, coins - f[a[idx]])){
         cout << a[idx];
         return trace(idx, coins-f[a[idx]]);
      }
   }

   return trace(idx+1, coins);
}


int32_t main(){_

   cin>>n>>m;
   f = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

   memset(dp, -1, sizeof dp);
   for (int i = 0; i < m; ++i)
      cin>>a[i];

   sort(a, a+m);
   reverse(a, a+m);
   int faltu = solve(0, n);
   trace(0, n);

   //make sure N size is correct!!!!!!!!!
   return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#include<string.h>
int main()
{
	char s[3];
	scanf("%s",s);
	if(strcmp(s,"SUN")==0)printf("7\n");
	if(strcmp(s,"MON")==0)printf("6\n");
	if(strcmp(s,"TUE")==0)printf("5\n");
	if(strcmp(s,"WED")==0)printf("4\n");
	if(strcmp(s,"THU")==0)printf("3\n");
	if(strcmp(s,"FRI")==0)printf("2\n");
	if(strcmp(s,"SAT")==0)printf("1\n");
	return 0;
}
	


Measured memory_bytes: 128
// In the name of GOD
#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";

#define     IOS         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define 	setprecn(x) cout<<fixed<<setprecision(x);
#define 	ll          long long int
#define 	pb          push_back
#define 	pll         pair<ll,ll>
#define 	vll         vector<ll>
#define 	ff          first
#define 	ss          second
#define 	all(a)      (a).begin(),(a).end()
#define 	sz(x)       (ll)x.size()
#define 	mod         1000000007
#define 	inf         10000000000000007
#define 	rep(i,n)    for(ll i=0;i<n;i++)
#define 	repe(i,a,b) for(ll i=a;i<b;i++)
#define 	lbnd        lower_bound
#define 	ubnd        upper_bound
#define 	bs          binary_search

ll power(ll a,ll b,ll m=mod)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	ll c=power(a,b/2,m);
	if(b%2==0)
		return((c%m)*(c%m))%m;
	return ((((c%m)*(c%m))%m)*(a%m))%m;
}

/********************************************************/
//	d.erase(unique(all(d)), d.end());

bool ispal(string s, ll x,ll y)
{
	ll i=x,j=y;
	while(i<=j)
	{
		if(s[i]!=s[j])
			return false;
		i++;
		j--;
	}
	return true;
}

int main()
{
	IOS;
	ll n,k,m,i,j,c=0,cs=0,t;
	t=1;

	// cin>>t;
	string s;
	while(t--)
	{
		cin>>s;
		n=s.length();
		// ll a[n];
		j=(n-1)/2;
		i=(n+3)/2;
		c=ispal(s,0,n-1) && ispal(s,0,j-1) && ispal(s,i-1,n-1);
		cout<<(c==1?"Yes":"No");

		
		cout<<"\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void insersion_sort(int *A, int N)
{
    int v;
    int j;

    for (int i = 1; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (k == N - 1)
            {
                printf("%d\n", A[k]);
            }
            else
            {
                printf("%d ", A[k]);
            }
        }
        v = A[i];
        j = i - 1;
        while (j >= 0 && A[j] > v)
        {
            A[j + 1] = A[j];
            j -= 1;
        }
        A[j + 1] = v;
    }
}

int main(void)
{
    int N;
    int A[100];
    int times;

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
    }

    insersion_sort(A, N);
    for (int i = 0; i < N; i++)
    {
        if (i == N - 1)
        {
            printf("%d\n", A[i]);
        }
        else
        {
            printf("%d ", A[i]);
        }
    }

    return 0;
}


Measured memory_bytes: 2112
class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.bit = [0] * (n + 1) # don't use bit[0]
        else:
            self.bit = [0] + init
            for i in range(1, n):
                self.bit[i + (i & -i)] += self.bit[i]

    def sum(self, i):
        '''
        Calculate bit[1] + ... + bit[i]
        '''
        S = 0
        while i > 0:
            S += self.bit[i]
            i -= i & -i
        return S

    def add(self, i, x):
        '''
        set bit[i] to be bit[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
def inversion_number(A):
    inv = 0
    bit = BIT(len(A))
    for i, x in enumerate(coord_compress(A)):
        inv += i - bit.sum(x+1)
        bit.add(x+1, 1)
    return inv

N = int(input())
*A, = map(int, input().split())
print(inversion_number(A))


Measured memory_bytes: 43668
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
int n,m,a,b,x[200100];
LL sum[200100],f[200100],bit1[200100],bit2[200100],ans;

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

void modify(LL *bit,int x,LL w)
{
    for (; x<=n; bit[x]=min(bit[x],w),x+=x&-x);
}

LL query(LL *bit,int x)
{
    LL ret=1LL<<60;
    for (; x; ret=min(ret,bit[x]),x-=x&-x);
    return ret;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b),ans=1LL<<60;
    repu(i,1,m)
        x[i]=getint();
    repu(i,2,m)
        sum[i]=sum[i-1]+abs(x[i]-x[i-1]);
    memset(bit1,80,sizeof(bit1));
    memset(bit2,80,sizeof(bit2));
    repu(i,1,m-1)
    {
        f[i]=sum[i]+min(abs(a-x[1])+abs(b-x[i+1]),abs(b-x[1])+abs(a-x[i+1]));
        f[i]=min(f[i],query(bit1,x[i+1])+sum[i]+x[i+1]);
        f[i]=min(f[i],query(bit2,n-x[i+1]+1)+sum[i]-x[i+1]);
        modify(bit1,x[i],f[i]-sum[i+1]-x[i]);
        modify(bit2,n-x[i]+1,f[i]-sum[i+1]+x[i]);
        ans=min(ans,f[i]+sum[m]-sum[i+1]);
    }
    printf("%lld\n",ans);
    return 0;
}

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

int prime[100000], primeNumber = 0;
bool isPrime[300010];

int main() {
  for (int i = 7; i < 300010; i += 7) {
    for (int j = i - 1; j <= i + 1; j += 2) {
      bool flag = true;
      for (int k = 0; k < primeNumber; k++) {
        if (j % prime[k] == 0) { flag = false; break; }
      }
      if (flag) prime[primeNumber++] = j;
    }
  }
  int n;
  while (1) {
    scanf("%d", &n);
    if (n == 1) break;
    printf("%d:", n);
    for (int i = 0; i < primeNumber; i++) {
      if (n % prime[i] == 0) printf(" %d", prime[i]);
      if (prime[i] > n) break;
    }
    printf("\n");
  }
}



Measured memory_bytes: 2900
#include <bits/stdc++.h>
using namespace std;
typedef long long in;
typedef pair<in,in> ii;
#define F first
#define S second
#define sqr(x) (x)*(x)
#define pb(x) push_back(x)
#define sz(x) (in)x.size()
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,x,y) for(in i=x;i<(y);++i)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

int main(){
    IOS;
    string s;
    cin >> s;
    rep(i,0,1<<(sz(s)-1)){
        in k = s[0]-'0';
        string r = "";
        rep(j,0,sz(s)-1){
            if(1<<j & i){
                r+='-';
                k-=s[j+1]-'0';
            }
            else{
                r+='+';
                k+=s[j+1]-'0';
            }
        }
        if(k == 7){
            string ans = "";
            ans+=s[0];
            rep(j,0,sz(s)-1){
                ans+=r[j];
                ans+=s[j+1];
            }
            cout << ans << "=7\n";
            break;
        }
    }
}

Measured memory_bytes: 256
fn main() {
    let mut true_value = {
        let mut temp_vec = Vec::<i32>::new();

        let n: usize = read();
        let v = read_vec::<i32>();
        let c = read_vec::<i32>();

        for i in 0..n {
            temp_vec.push(v[i] - c[i]);
        }

        temp_vec
    };

    let max: i32 = true_value.into_iter()
        .filter(|&x| { x > 0 })
        .sum();

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

#[warn(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[warn(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

#[warn(dead_code)]
fn read_mat<T: std::str::FromStr>(row: u32) -> Vec<Vec<T>> {
    let mut vec = Vec::new();

    for _i in 0..row {
        vec.push(read_vec::<T>());
    }

    vec
}


Measured memory_bytes: 4352
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]

from itertools import permutations
best = INF
for p in permutations(range(R)):
    score = 0
    for i in range(R-1):
        score += res[p[i]][p[i+1]]
    best = min(best, score)
print(int(best))

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};




int main(){
  
  int n,k;
  string s;
  cin >> n >> k >> s;
  s += '0';
  deque<int> lr;
  int last = 0;
  for(int i = 0;i < n;i++)if(s[i] != s[i+1])lr.push_back(last),last = i+1;
  s.erase(s.end()-1);
  for(int i = 0;i < k;i++){
    if(lr.empty())break;
    lr.pop_back();
    if(lr.empty())break;
    lr.pop_front();
  }
  if(!lr.empty())cout << n - (int)lr.size() << endl;
  else cout << n - 1 << endl;

  
  


  return 0;
}


Measured memory_bytes: 768
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kishan Sairam Adapa
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define ll long long int
#define MOD ((int)(1e9) + 7)

using namespace std;

class BAcCepted {
public:
    void solve(istream& cin, ostream& cout) {
        string s; cin >> s;
        bool flag = true;
        if(s[0] != 'A') flag = false;
        int n = s.length(); int cnt = 0;
        for(int i=2; i<n-1; i++) {
            if(s[i] == 'C') cnt++;
        }
        if(cnt != 1) flag = false;
        for(auto k: s) {
            if(k != 'A' && k != 'C') {
                if(k > 'z' || k  < 'a') flag = false;
            }
        }
        cout << ((flag) ? "AC\n": "WA\n");
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    BAcCepted solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    vector<long long> sums;
    vector<long long> differences;

    cin >> n;

    for (int i = 0; i < n; i++) {
        long long x;
        long long y;

        cin >> x >> y;

        sums.push_back(x + y);
        differences.push_back(x - y);
    }
    
    sort(sums.begin(), sums.end());
    sort(differences.begin(), differences.end());
    
    cout << max(abs(sums[0] - sums.back()), abs(differences[0] - differences.back())) << endl;

    return 0;
}


Measured memory_bytes: 6240
import java.util.*;

public class Main {
    public static void main(String[] args){
/*
Ａ大学は１フロア１０部屋、３階建ての公舎４棟を管理しています。
公舎の入居・退去の情報を読み込み、各部屋の入居者数を出力するプログラムを作成して下さい。
n件の情報が与えられます。各情報では、
４つの整数b, f, r, vが与えられます。
これは、b棟f階のr番目の部屋にv人が追加で入居したことを示します。
vが負の値の場合、-v人退去したことを示します
*/

        Scanner scanner = new Scanner(System.in);

        List<int[][]> builds = new ArrayList<int[][]>();
        for (int i=0; i<4; i++) {
            int[][] sb = new int[3][10];
            builds.add(sb);
        }

        int n = scanner.nextInt(); // row count
        for(int i=0; i<n; i++){
            int b = scanner.nextInt(); // school building no
            int f = scanner.nextInt(); // floor no
            int r = scanner.nextInt(); // no from left
            int v = scanner.nextInt(); // add value
            builds.get(b-1)[f-1][r-1] += v;
        }
        
        for(int i=0; i<4; i++){
            for(int j=0; j<3; j++){
                for(int k=0; k<10; k++){
                    int value = builds.get(i)[j][k];
                    System.out.print(" " + value );
                }
                System.out.println();
            }
            if (i != 3) { System.out.println("####################"); }
        }

        
        
    }
}



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

int main(int argc, char* argv[]) {
	int n;
	cin >> n;

	string ipt;
	cin >> ipt;

	int cnt = 0;
	for (int i = 1; i < n; i ++) {
		if (ipt[i - 1] != ipt[i])
			cnt ++;
	}

	cout << ++cnt << '\n';
	return 0;
}

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

int T;
int P;
int R;
char msg[114514];
int penalty[1145];
int correct[1145];
int teams[1145];
int wrong[1145][1419];

bool Compare(int a, int b) {
  if (correct[a] != correct[b]) return correct[a] > correct[b];
  if (penalty[a] != penalty[b]) return penalty[a] < penalty[b];
  return a < b;
}

int main() {
  while (1) {
    scanf("%d%d%d", &T, &P, &R);
    if ((T|P|R) == 0) return 0;

    for (int i=0; i<T; i++) teams[i] = i+1;
    fill(wrong[0], wrong[110], 0); 
    fill(correct, correct+110, 0); 
    fill(penalty, penalty+110, 0); 
  
    for (int i=0; i<R; i++) {
      int tid, pid, time;
      scanf("%d%d%d %s", &tid, &pid, &time, msg);
  
      string s(msg);
      if (s == "WRONG") {
        wrong[tid][pid] += 1;
      } else {
        penalty[tid] += wrong[tid][pid] * 1200 + time;
        correct[tid]++;
      }
    }
  
    sort(teams, teams+T, Compare);
    for (int i=0; i<T; i++) {
      int d = teams[i];
      printf("%d %d %d\n", d, correct[d], penalty[d]);
    }
  }
}

Measured memory_bytes: 3980