akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
class segtree:
    """
    segment tree
    value store as object type and get update function(merge_func) from outside

    Attributes
    ----------
    n : int
        Number of elements
    initialize_func : func
        function for initialization
    merge_func : func
        function for merge x and y to x(this merge is distruction update)

    Methods
    -------
    update(i, x)
        update tree[i] value to x
    get(a, b)
        get value from [a, b)
        include a but not include b, return a merged value
    """
    def __init__(self, n, initialize_func, merge_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        initialize_func : func
            function for initialization
        merge_func : func
            function for merge x and y to x(this merge is distruction update)
        """
        self.n = n
        self.initialize = initialize_func
        self.merge = merge_func
        n2 = 1  # n2はnより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [initialize_func() for _ in range(n2 << 1)]

    def update(self, index, x):
        index += self.n2
        self.tree[index] = self.merge(self.tree[index], x)
        while index > 1:
            # (index ^ 1) はiと1の排他的論理和(XOR)
            x = self.merge(x, self.tree[index ^ 1])
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            self.tree[index] = self.merge(self.tree[index], x)

    def get(self, a, b):
        result = self.initialize()
        q = [(1, 0, self.n2)]
        while q:
            k, left, right = q.pop()
            if a <= left and right <= b:
                result = self.merge(result, self.tree[k])
                continue
            m = (left + right) // 2
            k <<= 1
            if a < m and left < b:
                q.append((k, left, m))
            if a < right and left < m:
                q.append((k + 1, m, right))
        return result


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    max_A = 3 * 10 ** 5 + 1

    seg = segtree(max_A, lambda: 0, max)
    for a in A:
        next = seg.get(max(0, a - K), min(a + K + 1, max_A))
        seg.update(a, next + 1)
    print(seg.get(0, max_A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 166556
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);++i)
#define reps(i,n) for(int i = 1;i <= (n);++i)
using namespace std;
int main(){
  string s;
  cin >> s;
  if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
 
#define rp(i, k, n) for (int i = k; i < n; i++)
using ll = long long;
using ld = double;

template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7ll;
// const ll MOD = 998244353;
const double PI=3.14159265358979323846;



int main() {
    int m, n;
    cin >> n >> m;
    vector<string> A(n), B(m);
    string s;
    rp(i, 0, n) {
        cin >> s; A[i] = s;
    }
    rp(i, 0, m) {
        cin >> s; B[i] = s;
    }
    rp(i, 0, n-m+1) {
        rp(j, 0, n-m+1) {
            bool is_same = true;
            rp(k, 0, m) {
                rp(l, 0, m) {
                    if(B[k][l] != A[i+k][j+l]) {
                        is_same = false;
                        break;
                    }
                }
                if(is_same == false) break;
            }
            if(is_same) {
                cout << "Yes" << endl;
                return 0;
            }
        } 
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3532
/* author : akshatjai258 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define int ll
#define mod int(1e9 + 7)
#define inf int(1e9)
#define endl "\n"
#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 fi first
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
#define memf(a) memset(a, false, sizeof(a))
#define all(v) v.begin(), v.end()
#define se second
#define mp make_pair
#define pb push_back
#define w(x)  \
	int x;    \
	cin >> x; \
	while (x--)
#define ps(x, y) fixed << setprecision(y) << x
void prep()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/
}
int32_t main()
{
	prep();
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k<=a)
	{
		cout<<k;
	}
	else if(k<=(a+b))
	{
		cout<<a;
	}
	else if(k<=(a+b+c))
	{
		cout<<(a-(k-(a+b)));
	}
	return 0;
}



Measured memory_bytes: 3688
import java.util.*;

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

        final String YES_STR = "Yes";
        final String NO_STR = "No";
        if (y % 2 == 1) {
            System.out.println(NO_STR);
            return;
        }

        int totalFoot = 0;
        // [i]を亀の数、[x-i]を鶴の数とする
        for (int i = 0 ; i <= x ; i++) {
            totalFoot = (i * 4) + ((x - i) * 2);

            if (totalFoot == y) {
                System.out.println(YES_STR);
                return;
            }
        }
        System.out.println(NO_STR);
    }
}

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

using namespace std;

const int Maxn = 1e5+7;

int n, m;

struct Node
{
	int p, y, id;
	bool operator < (const Node &b) const
	{
		return p == b.p ? y < b.y : p < b.p;
	}
} a[Maxn];

struct res
{
	int p, rk;
} b[Maxn];

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i)
		scanf("%d%d", &a[i].p, &a[i].y), a[i].id = i;
	sort(a+1, a+m+1);
	for(int i = 1, cnt; i <= m; ++i)
	{
		if(a[i].p != a[i-1].p) cnt = 0;
		b[a[i].id].p = a[i].p;
		b[a[i].id].rk = ++cnt;
	}
	for(int i = 1; i <= m; ++i)
		printf("%06d%06d\n", b[i].p, b[i].rk);
	return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define ll long long
#define PI 3.141592653589
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EPS 1e-7
#define PII pair<int,int>
#define s second
#define f first
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
ll MOD = 1e9+7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
ll fast_power(ll x, ll p){
    ll res = 1;
    while(p > 0){
        if(p & 1){
            res = (res * x)%MOD;
        }
        p = p >> 1;
        x = (x*x)%MOD;
    }
    return res;
}
ll n, k;
struct Matrix{
    vector<vector<ll>> mat;
    int rows, cols;
    Matrix(vector<vector<ll>> values): mat(values), rows(mat.size()), cols(mat[0].size()) {}
    static Matrix indentity_Matrix(int n){
        vector<vector<ll>> values(n, vector<ll>(n, 0));
        for(int i = 0; i < n; i++){
            values[i][i] = 1;
        }
        return Matrix(values);
    }
    Matrix operator*(const Matrix &other) const{
        int o_row = other.rows, o_col = other.cols;
        vector<vector<ll>> ans(rows, vector<ll>(o_col, 0));
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < o_col; j++){
                for(int k = 0; k < cols; k++){
                    ans[i][j] += this->mat[i][k] * other.mat[k][j];
                    ans[i][j] %= MOD;
                }
            }
        }
        return Matrix(ans);
    }



};
Matrix fast_power(Matrix m, ll power){
    Matrix result = Matrix::indentity_Matrix(n);
    while(power){
        if(power&1){
            result = result * m;
        }
        m = m*m;
        power >>= 1;
    }

    return result;
}
int main() {
    IO;
    cin >> n >> k;
    vector<vector<ll>> v(n, vector<ll>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> v[i][j];
        }
    }
    Matrix ans = fast_power(Matrix(v), k);
    ll out = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n;  j++){
            out += ans.mat[i][j];
            out %= MOD;
        }
    }
    cout << out;




    return 0;
}


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

int main() {
  stack<int> stk;
  int n;
  while (cin >> n) {
    if (n) {
      stk.push(n);
    } else {
      cout << stk.top() << endl;
      stk.pop();
    }
  }
}


Measured memory_bytes: 3088
#include <stdio.h>
#define N 100
#define INF 100000

int min(int a,int b){
  if(a < b) return a;
  else return b;
}

int main(){
  int i,l,j,k,n,p[N + 1],m[N + 1][N + 1];
  scanf("%d",&n);
  for(i = 1;i <= n;i++) scanf("%d %d",&p[i - 1],&p[i]);
  for(i = 1;i <= n;i++) m[i][i] = 0;
  for(l = 2;l <= n;l++){
    for(i = 1;i <= n - l + 1;i++){
      j = i + l - 1;
      m[i][j] = INF;
      for(k = i;k <= j - 1;k++) m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] + p[
i - 1]*p[k]*p[j]);
    }
  }
  printf("%d\n",m[1][n]);
  return 0;
}

Measured memory_bytes: 636
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;
const int oo = 1e8+7;

int main() {
    
    int n;
    scanf("%d",&n);
    
    vi dp(3, 0);
    
    for(int i = 0; i < n; ++i) {
        
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        
        int fake1 = dp[0], fake2 = dp[1], fake3 = dp[2];
        dp[0] = max(fake2+a, fake3+a);
        dp[1] = max(fake1+b, fake3+b);
        dp[2] = max(fake1+c, fake2+c);
        
    }
    
    printf("%d\n", max(dp[0], max(dp[1], dp[2])));
    
    return 0;
}




Measured memory_bytes: 256
def step_shift(foot, next):
	if (not(foot[0]) and foot[1] > next) or (foot[0] and foot[1] < next):
		foot[2] += 1
	else:
		foot[0]^= 1
	foot[1] = next
	return foot

while 1:
	step = raw_input()
	if step == "#": break
	step = [int(s) for s in step]
	s_loc = {1:-1, 4:-1, 7:-1, 2:0, 8:0, 3:1, 6:1, 9:1} 
	foot_l = [False, s_loc[step[0]], 0]
	foot_r = [True, s_loc[step[0]], 0]
	for s in step[1:]:
		next = s_loc[s]
		foot_l = step_shift(foot_l, next)
		foot_r = step_shift(foot_r, next)
	print min(foot_l[2], foot_r[2])

Measured memory_bytes: 6460
s=input()
t=input()
a,b=[],[]
for i in s:
    a.append(ord(i))
for i in t:
    b.append(ord(i))
a.sort()
b.sort()
b=b[::-1]

for i in range(min(len(a),len(b))):
    if a[i]>b[i]:
        print("No")
        exit()
    elif a[i]<b[i]:
        print("Yes")
        exit()
print("Yes" if len(a)<len(b) else "No")

Measured memory_bytes: 3064
N, T = map(int, input().split())
CT = [list(map(int, input().split())) for _ in range(N)]

ans = 1001
for ct in CT:
    if ct[1] <= T:
        ans = min(ans, ct[0])

if ans == 1001:
    print('TLE')
else:
    print(ans)

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

using namespace std;

#define REP(i,m) for(ll i=0; i<m; i++)
#define FOR(i,n,m) for(ll i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

ll POW(ll a, ll b){
	if(b==1) return a;
	if(b%2==0) return POW(a*a%INF, b/2);
	return a*POW(a, b-1)%INF;
}

int main(){
	int p[100001] = { };
	p[0] = -1;
	p[1] = -1;
	REP(i, 100001){
		if(p[i] == 0){
			p[i] = 1;
			FOR(j, i, 100001){
				if(i*j > 100000) break;
				p[i*j] = -1;
			}
		}
	}
	int n, m;
	cin >> n >> m;
	ll c[100];
	c[0] = 1;
	REP(i, 99){
		c[i+1] = c[i] * (POW(i+1, INF-2) *(n+i) % INF)%INF;
		c[i+1] %= INF;
	}
	vector<int> v;
	REP(i, 100001){
		if(p[i] == 1){
			int c = 0;
			while(m%i==0){
				c++;
				m/=i;
			}
			v.pb(c);
		}
	}
	if(m != 1) v.pb(1);
	ll ans = 1;
	for(int i: v){
		(ans *= c[i]) %= INF;
	}
	cout << ans << endl;
	return 0;
} 


Measured memory_bytes: 768
#include<bits/stdc++.h>
        #define pb push_back
        #define mp make_pair
        #define ii pair<int,int>
        #define modulo 1000000007
        #define modulus 10000000000000003
        #define INF 100000000000000000
        #define int long long int
        using namespace std;
        
		vector<int> stones;
		vector<int> depe;
        int32_t main(){
			ios_base::sync_with_stdio(0);
			cin.tie(NULL);
			int n,a,k;
			cin >> n >> k;
			stones.resize(n+1);
			depe.resize(n+k+1,INF);
			for(int i=1;i<=n;i++){
				cin >> a;
				stones[i]=a;
				}
			depe[n]=0;
			for(int i=n-1;i>=1;i--){
				int mini=INF;
				for(int j=i+1;j<=i+k;j++){
					mini=min(mini,abs(stones[j]-stones[i])+depe[j]);
					}
				depe[i]=mini;
				}
			cout << depe[1];
			}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
  public static void main(String args[]) {
    final Scanner scanner = new Scanner(System.in);
    int a = scanner.nextInt();
    int b = scanner.nextInt();
    int result = 0;
    for (int i = 0; i < 2; i++) {
      if (a >= b) {
        result += a;
        a--;
      } else {
        result += b;
        b--;
      }
    }
    System.out.println(result);
  }
}

Measured memory_bytes: 23764
#include<iostream>
#include<string>
using namespace std;
int main(){
	string s;
	int n,len;
  	cin>>n;
    cin>>s;
  	len=s.length();
  	if(len%2==1){
    	cout<<"No";
      return 0;
    }
  	int p=len/2;
    for(int i=0;i<p;i++){
    	if(s[i]!=s[p+i]){
        	cout<<"No";
             return 0;
        }
    }
    cout<<"Yes";
  	
}

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

bool can_fill(int mass, int small, int large) {
    for (int i = 0; small*i <= mass; i++) {
        if ((mass - small*i) % large == 0) return true;
    }
    return false;
}

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    double max_sat = -1.0;
    int ans1, ans2;
    for (int w = 1; w <= f/100; w++) {
        for (int s = 0; s <= e*w; s++) {
            if (100*w + s <= f &&
                    can_fill(w, a, b) && can_fill(s, c, d)) {
                double sat = 100.0*s / (100*w + s);
                if (sat > max_sat) {
                    max_sat = sat;
                    ans1 = 100*w + s; ans2 = s;
                }
            }
        }
    }

    printf("%d %d\n", ans1, ans2);
}

Measured memory_bytes: 256
x, a, b =map(int, input().split())
n = int(input())
voice = [input() for _ in range(n)]
for i in voice:
  if i == "nobiro":
    x += a
  elif i == "tidime":
    x += b
  elif i == "karero":
    x = 0
  if x < 0:
    x = 0
print(x)


Measured memory_bytes: 5616
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n = I()
lis = list(range(1,n+1))
a,b = None,None
P = readInts()
Q = readInts()
i = 0
for A in permutations(lis,n):
    if list(A) == P == Q:
        a,b = i,i
    elif list(A) == Q:
        b = i
    elif list(A) == P:
        a = i
    i += 1
print(abs(a-b))


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

using namespace std;

int main() {
  int n = 0; cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }
  int cnt = 0;
  for (int i=0; i<n; i++) {
    if (a.at(a.at(i)-1) == i+1) {
      cnt++;
    }
  }
  cout << cnt / 2 << endl;
  return 0;
}


Measured memory_bytes: 640
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = int(input())
def sub(n, b):
    """nのb進数表記したときの各桁
    n = sum(pow(b,i) * ans[i])
    """
    ans = []
    while n>0:
        n,v = divmod(n, b)
        ans.append(v)
    return ans
ans = None
for b in range(2,n+1):
    if b**2>n:
        break
    if sum(sub(n, b))==s:
        ans = b
        break
if ans is None:
    ans = float("inf")
    if n==s:
        ans = s+1
    for p in range(1,n+1):
        if p**2>n:
            break
        if (n+p-s)%p==0:
            b = (n+p-s)//p
            q = s - p
            if b**2>n and 0<=q<b and p<b and b*p+q==n and p+q==s:
                ans = min(ans, b)
            else:
                continue
if ans is None or ans==float("inf"):
    ans = -1
print(ans)

Measured memory_bytes: 73668
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>

using namespace std;

struct node {
	int left, right, per;
};

void preorder(int x, vector<node> &nd) {
	cout << " " << x;
	if (nd[x].left != -1) preorder(nd[x].left, nd);
	if (nd[x].right != -1) preorder(nd[x].right, nd);
}

void inorder(int x, vector<node> &nd) {
	if (nd[x].left != -1) inorder(nd[x].left, nd);
	cout << " " << x;
	if (nd[x].right != -1) inorder(nd[x].right, nd);
}

void postorder(int x, vector<node> &nd) {
	if (nd[x].left != -1) postorder(nd[x].left, nd);
	if (nd[x].right != -1) postorder(nd[x].right, nd);
	cout << " " << x;
}

int main() {
	int n, st = 0;
	cin >> n;
	vector<node> nd(n);
	for (int i = 0; i < n; i++) nd[i].per = -1;
	for (int i = 0; i < n; i++) {
		int id, left, right;
		cin >> id >> left >> right;
		nd[id].left = left;
		nd[id].right = right;
		if (left != -1) nd[left].per = id;
		if (right != -1) nd[right].per = id;
	}
	while (nd[st].per != -1) st = nd[st].per;
	cout << "Preorder" << endl;
	preorder(st, nd);
	cout << endl;
	cout << "Inorder" << endl;
	inorder(st, nd);
	cout << endl;
	cout << "Postorder" << endl;
	postorder(st, nd);
	cout << endl;
}

//node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node

Measured memory_bytes: 3088
// No.191212031920
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;

inline void inc(int &x, const int &y) {
    x += y; if (x >= Mod) x -= Mod;
}

int nxt[7][2];
int n, f[7], g[7];
char s[300300];

int main() {
#ifdef LOCAL_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    scanf("%s", s + 1);
    n = strlen(s + 1);
    assert(n & 1);

    if (n == 1) puts(s[1] == '0' ? "0" : "1"), exit(0);

    nxt[0][0] = 1, nxt[0][1] = 3;
    nxt[1][0] = 2, nxt[1][1] = 0;
    nxt[2][0] = 1, nxt[2][1] = 1;
    nxt[3][0] = 4, nxt[3][1] = 6;
    nxt[4][0] = 5, nxt[4][1] = 3;
    nxt[5][0] = 4, nxt[5][1] = 4;
    nxt[6][0] = 6, nxt[6][1] = 6;

    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        memset(g, 0, sizeof g);
        for (int j = 0; j < 7; ++j) if (f[j]) {
            if (s[i] ^ '1') inc(g[nxt[j][0]], f[j]);
            if (s[i] ^ '0') inc(g[nxt[j][1]], f[j]);
        }
        swap(g, f);
    }

    cout << 1ll * (f[6] + f[3]) % Mod;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef pair<int,int> P;
struct edge{
	int to,cap,cost,rev;
	edge(int a,int b,int c,int d) : to(a),cap(b),cost(c),rev(d) {}
};
const int MAX_V=366,INF=1e8;
int V=366;			//??£??\!!
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void init(){
	rep(i,MAX_V) G[i].clear();
}
void add_edge(int from, int to, int cap, int cost){
	edge e1=edge(to,cap,cost,G[to].size()),e2=edge(from,0,-cost,G[from].size());
	G[from].push_back(e1);
	G[to].push_back(e2);
}
int min_cost_flow(int s, int t, int f){
	int res=0;
	fill(h,h+V,0);
	rep(v,V){
		for(edge e:G[v]){
			if(e.cap>0) chmin(h[e.to],h[v]+e.cost);
		}
	}
	while(f>0){
		priority_queue< P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first) continue;
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF) return -1;
		for(int v=0;v<V;v++) h[v]+=dist[v];
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
int main(){
	while(true){
		int N;
		cin>>N;
		if(N==0) break;
		init();
		rep(i,N){
			int a,b,c;
			cin>>a>>b>>c;
			add_edge(a-1,b,1,-c);
		}
		rep(i,365) add_edge(i,i+1,2,0);
		cout<<-min_cost_flow(0,365,2)<<endl;
	}
}

Measured memory_bytes: 1340
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define TEST cout << "ococo" << endl;
using namespace std;

int main(void){
	int h,w,n,i = 1;
	cin >> h >> w >> n;
	while (i++) {
		if(max(h,w) >= n){
			cout << 1 << endl;
			return 0;
		}
		if(i * max(h,w) >= n){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

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

const int MAX = 100;
const int INF = (1<<12);

bool isPrime(int x){
  if (x == 2) return true;
  if (x < 2 || (x%2) == 0) return false;

  int i = 3;
  while (i <= sqrt(x)){
    if(x%i == 0) return false;
    i += 2;
  }
  return true;
}


int main() {
  int x;
  cin >> x;
  int i;
  for (i = x; i <= 100003; i++)
  {
    if(isPrime(i)) break;
  }
  cout << i << endl;
  return 0;
}

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

struct Dice
{
	int Top, Front, Right, Left, Back, Bottom;
};


void roll (Dice &d1, int r);
bool equal(Dice d1, Dice d2);

int main()
{
	Dice d1, d2;	
	cin >> d1.Top >> d1.Front >> d1.Right >> d1.Left >> d1.Back >> d1.Bottom;
	cin >> d2.Top >> d2.Front >> d2.Right >> d2.Left >> d2.Back >> d2.Bottom;
	while (d1.Top != d2.Top || d1.Front != d2.Front)
		roll(d1, rand()%4);
	if (equal(d1, d2))
		cout << "Yes" << endl;
	else 
		cout << "No" << endl;
	return 0;
}

void roll (Dice &d1, int r)
{
	switch (r)
		{
			case 0:	  swap(d1.Top, d1.Back); 
					  swap(d1.Back, d1.Bottom);
					  swap(d1.Bottom, d1.Front);
					  break;
			case 1:	  swap(d1.Top, d1.Front);
					  swap(d1.Front, d1.Bottom);
					  swap(d1.Bottom, d1.Back);
					  break;
			case 2:   swap(d1.Top, d1.Left);
					  swap(d1.Left, d1.Bottom);
					  swap(d1.Bottom, d1.Right);
					  break;
			case 3:   swap(d1.Top, d1.Right);
					  swap(d1.Right, d1.Bottom);
					  swap(d1.Bottom, d1.Left);
					  break;
		}
}

bool equal(Dice d1, Dice d2)
{
	if (d1.Right != d2.Right)
		return false;
	else if (d1.Left != d2.Left)
		return false;
	else if (d1.Back != d2.Back)
		return false;
	else if (d1.Bottom != d2.Bottom)
		return false;
	return true;
}



Measured memory_bytes: 3096
/* ex8_1 
melo */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 11
typedef struct{
    int size;//最大何個までstackに入るか
    int count;//現在のデータの数
    char data[SIZE];//データ配列
    char *top;//一番上のポインタ
} stack;
void initialize_stack(stack *stk);//スタックの初期化
void revprint_stack(stack *stk);//古いものからプリントする
void push(stack *stk,char input);//inputを一番上に格納
char pop(stack *stk);//一番上を取り出す
stack stk;
int main(void){
    char key[SIZE];//打ち込む文字
    int i;//for文用
    initialize_stack(&stk);//初期化
    scanf("%s",key);//打ち込んだ文字を入力
    for(i=0;i<strlen(key);i++){
        if(key[i]!='B'){//Bでなかった場合
            push(&stk,key[i]);//スタックに文字を格納
        }
        else{//Bだった場合
            pop(&stk);//１文字取り出す
        }
    }
    revprint_stack(&stk);//古いものからプリントする
    return 0;//正常終了
}
void initialize_stack(stack *stk){//初期化
    stk->count=0;//個数をゼロに
    stk->size=SIZE;//最大のサイズ
    stk->top=&(stk->data[SIZE]);//配列の最終要素の手前
}
void push(stack *stk,char input){//inputをスタックにいれる
    if(stk->count >= stk->size){//オーバーフローするとき
        printf("Error: stack overflow. (x=%c)\n", input);
        exit(1);// プログラムの終了
    }
    else{
        stk->top--;//topを一つ上にあげる
        *(stk->top)=input;//そこにデータを格納
        stk->count++;//現在のデータ数を増やす
    }
}
char pop(stack *stk){//一番上の要素を取り出す
    char input;//一番上の要素をいれる箱
    if(stk->count<=0){//アンダーフローするとき
        return '\t';//\tを返す
    }
    else{
        input=*(stk->top);//topからデータを取り出す
        stk->top++;//topを一つしたに下げる
        stk->count--;//現在のデータ数を減らす
        return input;//これ出したデータを返す
    }
}
void revprint_stack(stack *stk){//古いものからプリントする
    char *ptr;//ポインタを用意
    ptr =stk->top;//topの位置
    ptr+=stk->count-1;//topの一からcount-1したの位置に移動する（最も古いデータ）
    for(int i=stk->count-1;i>=0;i--){//count繰り返す
        printf("%c", *ptr--);//古いものからプリント
    }
    printf("\n");//改行
}


Measured memory_bytes: 1604
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
const int N=3005;
ll dp[N][N][2];
ll solve(vector<ll>&a,int c,int start,int end)
{
  if(start>end)
    return 0;

  if(dp[start][end][c])
    return dp[start][end][c];

  ll ans=0;  
  if(c==0)
  {
    ans=a[start]+solve(a,1-c,start+1,end);
    ans=max(ans,a[end]+solve(a,1-c,start,end-1));
  }
  else
  {
    ans=solve(a,1-c,start+1,end)-a[start];
    ans=min(ans,solve(a,1-c,start,end-1)-a[end]);
  }

  return dp[start][end][c]=ans;

}


int main()
{
  ll n;
  cin>>n;
  vector<ll> a(n);
  for(int i=0;i<n;i++)
    cin>>a[i];

  vector<vector<ll>>dp(n,vector<ll>(n,INT_MIN));

  ll ans=solve(a,0,0,n-1);
  cout<<ans<<endl;
}


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

using namespace std;

int main(int argc, const char *argv[]) {
  string s;
  cin >> s;

  if(s[2] == s[3] && s[4] == s[5]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    int n, a, b;cin >> n >> a >> b;
    string s;cin >> s;
    int ac = 0;
    int bc = 0;
    for(auto c : s){
        if(c == 'a'){
            if(ac+bc < a+b){
                cout << "Yes" << endl;
                ac++;
            }else{
                cout << "No" << endl;
            }
        }else if(c == 'b'){
            if(ac+bc < a+b && bc < b){
                cout << "Yes" << endl;
                bc++;
            }else{
                cout << "No" << endl;
            }
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 848
A,B,C, D = map(int, input().split())
def gcd(n, m ):
    if n%m == 0:
        return m
    else:
        return gcd(m, n%m)
gcdCD = gcd(C, D)
lcmCD = int(C * D /gcdCD)
def count(start , end , n):
    return end//n -(start-1)//n
numC = count(A, B, C)
numD = count(A, B, D)
numCD = count(A,B, lcmCD)
warikireCD = numC + numD - numCD
print(B- A + 1 - warikireCD)


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

int main() {
	vector<int> v;
	int x;
	int count = 1;
	while(1) {
		cin >> x;
		if (x == 0) break;
		else v.push_back(x);
	}
	for (auto n: v) {
		cout << "Case " << count << ": " << n << endl;
		count++;
	}
	return 0;
}

Measured memory_bytes: 3120
from collections import deque
N = int(input())
V = set()
E = {}

for _ in range(N):
  x,y = map(int, input().split())
  y += 100010
  V.add(x)
  V.add(y)
  if x not in E:
    E[x] = [y]
  else:
    E[x].append(y)
  if y not in E:
    E[y] = [x]
  else:
    E[y].append(x)

#print(V)
#print(E)
## DFS
visited = [ False ] * 200020
willSearch = [ False ] * 200020
Q = deque()
ans = 0
for v in V:
  if visited[v]:
    continue

  Q.append(v)
  xcount, ycount = 0,0
  edge_count = 0
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True

    if now > 100005:
      ycount += 1
    else:
      xcount += 1
      
    for nxt in E[now]:
      edge_count += 1
      if visited[nxt] or willSearch[nxt]:
        continue
      #print(v,now,nxt)

      willSearch[nxt] = True

      Q.append(nxt)
  #print(v,xcount, ycount, edge_count)
  ans += xcount * ycount
  ans -= edge_count // 2
  
print(ans)

Measured memory_bytes: 39400
#include <iostream>
#include <cstdio>
using namespace std;
int d[11][11], f[111][111];

int main(void)
{
    int A, B, ok = 1;
    scanf("%d %d", &A, &B);
    for(int i = 1; i <= A; i++)
        for(int j = 1; j <= B; j++)
            scanf("%d", &d[i][j]);
    for(int x = 1; x <= A; x++)
    for(int y = 1; y <= B; y++)
    for(int a = 0; a <= 100; a++)
    for(int b = 0; b <= 100; b++)
    f[a][b] = max(f[a][b], d[x][y] - x * a - y * b);
    for(int x = 1; x <= A; x++)
    for(int y = 1; y <= B; y++)
    {
        int tmp = 1111;
        for(int a = 0; a <= 100; a++)
        for(int b = 0; b <= 100; b++)
            tmp = min(x * a + y * b + f[a][b], tmp);
        if(tmp != d[x][y]) ok = 0;
    }
    if(!ok) puts("Impossible");
    else
    {
        puts("Possible");
        printf("202 10401\n");
        for(int i = 1; i <= 100; i++) printf("%d %d X\n", i, i + 1);
        for(int i = 102; i <= 201; i++) printf("%d %d Y\n", i, i + 1);
        for(int i = 1; i <= 101; i++)
            for(int j = 102; j <= 202; j++)
                printf("%d %d %d\n", i, j, f[i-1][202-j]);
        printf("1 202\n");
    }
    return 0;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
import sys
n=int(input())
a=0
for i in range(n):
    say=input()
    if(say=='A'):
         a+=1
    else:
        a-=1
        if(a<0):
            print("NO")
            sys.exit()
if a:
    print("NO")
else:
    print("YES")

Measured memory_bytes: 7680
# seishin.py
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

MOD = 998244353

ans = pow(2, N, MOD) - 1 - N
u = set()
for i in range(N):
    xi, yi = P[i]
    for j in range(i+1, N):
        xj, yj = P[j]
        if (i, j) in u:
            continue
        cnt = 0
        Q = {i, j}
        for k in range(N):
            xk, yk = P[k]
            if (xj - xi)*(yk - yi) == (xk - xi)*(yj - yi):
                cnt += 1
                Q.add(k)
        for p in Q:
            for q in Q:
                u.add((p, q))
        ans -= pow(2, cnt, MOD) - cnt - 1
print(ans % MOD)

Measured memory_bytes: 7660
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
// int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll n;
  cin >> n;
  string s;
  while(n){
    n--;
    s.push_back('a'+n%26);
    n/=26;
  }
  reverse(s.begin(),s.end());
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3652
N = int(input())

xun = []
for _ in range(N):
	x,u = input().split()
	xun.append([x,u])
	
sumYen = 0
for xu in xun:
	if xu[1] == "BTC":
		sumYen += (float(xu[0])*380000)
	else:
		sumYen += int(xu[0])
		
print(sumYen)

Measured memory_bytes: 3060
from collections import deque

N, M = map(int, input().split())
E = {u: set() for u in range(1, N + 1)}
for i in range(M):
    u, v = map(int, input().split())
    E[u].add(v)
S, T = map(int, input().split())

X = {(u, i): set([(v, (i + 1) % 3) for v in E[u]])
     for u in E for i in range(3)}

# bfs
queue = deque([((S, 0), 0)])
visited = set()

while len(queue) > 0:
    u, n = queue.popleft()
    if u in visited:
        continue
    visited.add(u)
    if u == (T, 0):
        print(n // 3)
        exit()
    for v in X[u]:
        queue.append((v, n + 1))

print(-1)


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

int v[3];

int main()
{
    cin >> v[0] >> v[1] >> v[2];
    sort(v, v + 3);

    if(v[0] == 5 && v[1] == 5 && v[2] == 7)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';

    return 0;
}


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

int main() {

	int D;
	cin >> D;
	int N = 26;
	vector<int> C(N,0); // C[i]
	vector<vector<int> > S(D,vector<int>(N,0)); // S[d][i]
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	for (int d = 0; d < D; d++) {
		for (int i = 0; i < N; i++) {
			cin >> S[d][i];
		}
	}
	for (int d = 0; d < D; d++) {
		int i = 0;
		for (int j = 1; j < N; j++) {
			if (S[d][i] < S[d][j]) i = j;
		}
		cout << i + 1 << endl;
	}

	return(0);
}


Measured memory_bytes: 3680
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <sstream>
 
#define For(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  For(i,0,n)
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define SORT(c) sort((c).begin(),(c).end())
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)
 
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define WARU 1000000007;
 
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

int main() {
    int n;
    cin >>n;
    if( n < 1200){
        cout << "ABC" << endl;
    }else if (n < 2800){
        cout << "ARC" <<endl;
    }else
    cout << "AGC" <<endl;

    return 0;
}

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

int main()
{
    ll n;cin>>n;
    ll a1,a2,b1,b2;
    for(ll i=0;i<n;i++){
        ll p,q;
        cin>>p>>q;
        if(i==0){
            a1=p+q;
            a2=p+q;
            b1=(p-q);
            b2=b1;
        }
        a1=max(a1,p+q);
        a2=min(a2,p+q);
        b1=max(b1,(p-q));
        b2=min(b2,(p-q));
    }
    ll ans=max(a1-a2,b1-b2);
    cout<<ans<<endl;
}


Measured memory_bytes: 3632
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int n = sc.nextInt();
			long[] a = new long[n];
			long[] num = new long[n+1];
			
			for(int i=0;i<n;i++) {
				a[i] = sc.nextInt();
				num[(int)a[i]-1]++;
			}
			
			long aret = 0;
			
			for(int i=0;i<n;i++) {
				if(num[i]<=1) {
					continue;
				}else {
					aret+=num[i]*(num[i]-1)/2;
				}
				
			}
			
			for(int i=0;i<n;i++) {
				System.out.println(aret-num[(int)a[i]-1]+1);
			}
			
			
	    }
				
	}


Measured memory_bytes: 103052
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int h, w;
	while (cin >> h >> w && (h || w)) {
		VS tile(h); vector<VB> visited(h, VB(w));
		rep(i, h)cin >> tile[i];

		PII now = mp(0, 0), ans = mp(-1, -1); bool loop = false;
		while (!loop && ans.first == -1 && ans.second == -1) {

			if (visited[now.second][now.first])loop = true;
			visited[now.second][now.first] = true;

			switch (tile[now.second][now.first]) {
			case '.':
				ans = now;
				break;
			case '>':
				now.first++;
				break;
			case '<':
				now.first--;
				break;
			case '^':
				now.second--;
				break;
			case 'v':
				now.second++;
				break;
			}

		}

		if (loop)puts("LOOP");
		else Cout2(ans.first, ans.second);
	}
}


Measured memory_bytes: 3008
// 解説を見た
// 数列を昇順で見ていったとき、a[i]を置くことが出来るのはa[i]-t以上の要素の直前、もしくは末尾
// これは二分探索で計算できる
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
    int n, t;
    cin >> n >> t;
    vector<int> v(n);
    for(int i = 0; i < n; i++)  cin >> v[i];
    sort(v.begin(), v.end());
    ll ans = 1, mod = 1000000007;
    for(int i = 1; i < n; i++){
        int j = i-(lower_bound(v.begin(),v.end(),v[i]-t)-v.begin())+1; // (a[i]-t以上の要素数) + 末尾分の1
        ans *= j;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "No" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

class Dijkstra{
    private:
    typedef std::pair<long long,int> P;
    std::vector<std::vector<P>> G;
    int V;
    //long long INF = (1LL<<61);
    std::priority_queue<P,std::vector<P>,std::greater<P>> que;
    
    public:
    void init(std::vector<std::pair<std::pair<int,int>,long long>> edge){
        //頂点数を決定する
        V=0;
        for(int i=0;i<edge.size();i++){
            V=std::max(V,edge[i].first.first+1);
            V=std::max(V,edge[i].first.second+1);
        }
        
        //辺集合を扱いやすい形式に変換する
        G.resize(V);
        for(int i=0;i<edge.size();i++){
            int from=edge[i].first.first,to=edge[i].first.second;
            long long cost=edge[i].second;
            G[from].push_back({cost,to});
        }
    }
    
    std::vector<long long> solve(int s){
        std::vector<long long> d;
        //INFで初期化する
        for(int i=0;i<V;i++){
            d.push_back(INF);
        }
        d[s]=0;
        que.push({0,s});
        //queは{cost,to}をコストが小さい順に出す
        while(!que.empty()){
            P p = que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first)continue;
            for(int i=0;i<G[v].size();i++){
                P e = G[v][i];
                if(d[e.second]>d[v]+e.first){
                    d[e.second] = d[v]+e.first;
                    que.push({d[e.second],e.second});
                }
            }
        }
        return d;
    }
    
    //init:{{int,int},longlong}のvectorを渡すことで有向グラフを構築する
    //solve:始点を渡すとinitで構築したグラフでダイクストラをし、コストのvectorを返す
};

signed main(void){
    int H,W;
    string S[57];
    cin >> H >> W;
    REP(i,H){
        cin >> S[i];
    }
    
    vector<pair<pair<int,int>,int>> edges;
    REP(i,H){
        REP(j,W){
            if(S[i][j]!='.')continue;
            if(j!=W-1 && S[i][j+1]=='.'){
                edges.push_back({{i*100+j,i*100+(j+1)},1LL});
                edges.push_back({{i*100+(j+1),i*100+j},1LL});
            }
            if(i!=H-1 && S[i+1][j]=='.'){
                edges.push_back({{i*100+j,(i+1)*100+j},1LL});
                edges.push_back({{(i+1)*100+j,i*100+j},1LL});
            }
        }
    }
    if(edges.size()==0){
        cout << -1 << endl;
        return 0;
    }
    Dijkstra daiku;
    daiku.init(edges);
    vector<int> d=daiku.solve(0);
    int cost=d[(H-1)*100+(W-1)];
    int black=0;
    REP(i,H){
        REP(j,W){
            if(S[i][j]!='.'){
                black++;
            }
        }
    }
    if(cost==INF){
        cout << -1 << endl;
        return 0;
    }
    //cout << cost << endl;
    cout << H*W-(cost+1)-black << endl;
    return 0;
}



Measured memory_bytes: 1020
#入力
N = int(input())

red_x = []
red_y = []
for i in range(N):
    a = list(map(int, input().split()))
    red_x += [a]
    red_y += [a[::-1]]
red_x.sort(reverse = False)
red_y.sort(reverse = False)
#print (red_x, red_y)


blue_x = []
blue_y = []

for i in range(N):
    a = list(map(int, input().split()))
    blue_x += [a]
    blue_y += [a[::-1]]
blue_x.sort(reverse = False)
blue_y.sort(reverse = False)
#print (blue_x, blue_y)

def judge_x(m): #blue[m]がペアを作れるかどうかをTrue or Falseで返す x優先
    INF = 10 ** 9
    count = 0
    memo = -1
    for i in range(N):
        if blue_x[m][0] > red_x[i][0]: #x座標が条件を満たすか確認
            
            #条件を満たす中で最大のy座標を探す

            #y座標の確認をしてない！！！！ｓ
            #
            if memo < red_x[i][1] and blue_x[m][1] > red_x[i][1]: 
                count = 1
                memo = max(memo, red_x[i][1]) #最も大きいy座標を記録
                memo_i = i
    if count == 0: #iのループを回してもカウントが増えない=x座標が条件を満たすことが一度もない
        return False
    else: #少なくとも一回は条件を満たした。
        red_x[memo_i][0] = INF #使ったものをINFで書き換え
        red_x[memo_i][1] = INF #使ったものをINFで書き換え
#        print (red_x)
        return True
    return False

def judge_y(m): #blue[m]がペアを作れるかどうかをTrue or Falseで返す y優先
    INF = 10 ** 9
    for i in range(N):
        if blue_y[m][1] > red_y[i][1]:
            if blue_y[m][0] > red_y[i][0]:
                red_y[i][1] = INF
                return True
        else:
            pass
    return False

count_x = 0
for s in range(N): #blue内のxが最も小さいののから着目
    if judge_x(s):
        count_x += 1
print (count_x)

#count_y = 0    
#for t in range(N):
#    if judge_y(t):
#        count_y += 1
#print (count_y)

#print (max(count_x, count_y))
#print (judge(0))
#print (judge(1))
#print (judge(2))
#print (judge(3))
#print (judge(4))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	/*ll t;cin>>t;
	while(t-->0)
    {
    }*/
    int a;cin>>a;
    string s;cin>>s;
    if(a>s.size())
    {
        a=s.size();
    }
    for(int i=0;i<a;i++)
    {
        cout<<s[i];
    }
    if(s.size()>a)
    cout<<"...";
}


Measured memory_bytes: 3588
from sys import stdin

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

rate = [0]*8
f = 0

for i in range(n):
    if 3199 < a[i]:
        f += 1
    else:
        rate[int((a[i]/400))] = 1

s = sum(rate)
min = s if 0 < s else 1
max = s+f

print(min, max)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;

int n, m; vector <int> g[MAXN];

int main(){
	int i, j, u, v; bool to1, ton;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; ++ i){
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	for(i = 2; i < n; ++ i){
		for(j = 0, to1 = ton = false; j < int(g[i].size()); ++ j)
			if(g[i][j] == 1) to1 = true;
			else if(g[i][j] == n) ton = true;
		if(to1 && ton) break;
	} printf("%s\n", i < n ? "POSSIBLE" : "IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 12016
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def digit_sum(n):
    res = 0
    while n > 0:
        res += n % 10
        n //= 10
    return res


def resolve():
    n = input()
    l = len(n)

    res = 0
    for i in range(l):
        if i == 0:
            res += int(n[i]) - 1
        else:
            res += 9

    res = max(res, digit_sum(int(n)))
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>


int main(){
    long long Q,H,S,D,N;
    long long res=0;

    scanf("%lld %lld %lld %lld",&Q,&H,&S,&D);

    scanf("%lld",&N);

    if(2*Q<H){
        H = 2*Q;
    }
    if(4*Q<S){
        S = 4*Q;
    }
    if(8*Q<D){
        D = 8*Q;
    }
    if(2*H<S){
        S = 2*H;
    }
    if(4*H<D){
        D = 4*H;
    }
    if(2*S<D){
        D = 2*S;
    }


    if(N%2==0){
        res += (N/2)*D;
    }
    if(N%2==1){
        res += (N/2)*D;
        res += S;
    }

    printf("%lld\n",res);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int main(){
  int h, n; cin >> h >> n;
  vector<int> a, b;
  for(int i=0; i<n; i++){
    int ai, bi; cin >> ai >> bi;
    a.push_back(ai);
    b.push_back(bi);
  }
  vector<vector<int>> dp(2000, vector<int>(20000, INF));
  dp[0][0]=0;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=h; j++){
      if(dp[i][j]>dp[i-1][j]) dp[i][j]=dp[i-1][j];
      if(j+a[i-1]>h && dp[i][h]>dp[i][j]+b[i-1]) dp[i][h]=dp[i][j]+b[i-1];
      else if(dp[i][j+a[i-1]]>dp[i][j]+b[i-1]) dp[i][j+a[i-1]]=dp[i][j]+b[i-1];
    }
  }  
  cout << dp[n][h];
  return 0;
}

Measured memory_bytes: 156672
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int area = a*b;
        int length = a*2 + b*2;
        System.out.println(area + " " + length);
        sc.close();
    }
}


Measured memory_bytes: 26080
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    int numa, numb;
    cin >> numa >> numb;
    cout << (numa*(numa-1))/2+(numb*(numb-1))/2 << endl;
    return 0;
}

Measured memory_bytes: 888