akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int main(){
  int N;cin>>N;
  vi A;
  int sum=0;
  for (int i=0;i<N;++i){
    int a;cin>>a;A.push_back(a);
    sum+=a;
  }
  for (int i=0;i<N;++i){
    
  }

  bitset<2001*2001> dp;
  dp.set(0);
  for (int i=0;i<N;++i){
    dp=(dp| (dp<<A[i]));
  }

  int begin=(sum%2==0) ? sum/2 : sum/2+1;

  for (int i=begin;i<=sum;++i){
    if(dp[i]){
      cout << i << endl;
      return 0;
    }
  }
}

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

int main()
{
  char s[10000];
  int x,i,j;
  for(;~scanf("%s",s);)
    {
      for(i=j=x=0;s[x+2]!='\0';x++)
	{
	  if(s[x]=='J' && s[x+1]=='O' && s[x+2]=='I')
	    j++;
	  if(s[x]=='I' && s[x+1]=='O' && s[x+2]=='I')
	    i++;
	}
      printf("%d\n%d\n",j,i);
    }
  exit(0);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;

void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const ll MAXN = 1e6 + 10;
const ll N = 4000 + 10;
const ll MN = 200 + 10;
const ll mod = 1e6;

ll w[MAXN] , a[MAXN] , dp[2][MAXN];

int main()
{
	faster();
	int n, W;
	cin >> n >> W;
	for (int i = 0; i < n; i++)
		cin >> w[i + 1] >> a[i + 1];
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			dp[i % 2][j] = dp[(i - 1) % 2][j];
			if(j >= w[i])
				dp[i % 2][j] = max(dp[i % 2][j] ,dp[(i - 1) % 2][j - w[i]] + a[i]);
		}
	}
	cout << dp[n % 2][W] << endl;
}

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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
const long long INF = 1LL << 60;

struct Edge {
  int to;
  ll cost;
};
using Graph = vector<vector<Edge>>;

vector<bool> can_reach(const Graph& G, int start) {
  ll n = G.size();
  vector<bool> ans(n);
  queue<int> que;

  que.push(start);
  ans[start] = true;

  while (!que.empty()) {
    int index = que.front();
    que.pop();
    for (const auto& it : G[index]) {
      if (ans[it.to] == false) {
        que.push(it.to);
        ans[it.to] = true;
      }
    }
  }

  return ans;
}

// Bellman Ford
// G: グラフ
// rev: 逆辺のグラフ(負の閉路検出用)
// start: 始点
// goal: 終点
// 戻り値: goalに行くまでの最小コスト。負の閉路が存在する場合は-INFとなる。
ll bellman_ford(const Graph& G, const Graph& rev, const int start, const int goal) {
  const int n = G.size();

  // 始点からそこまで行くのにかかるのコスト
  vector<ll> cost(n, INF);
  cost[start] = 0;

  for (int i = 0; i < n; i++) {
    // すべての辺を走査
    for (int from = 0; from < n - 1; from++) {
      if (cost[from] == INF) {
        continue;
      }
      for (auto e : G[from]) {
        // 更新
        if (cost[e.to] > cost[from] + e.cost) {
          cost[e.to] = cost[from] + e.cost;
        }
      }
    }
  }

  vector<ll> cost_middle = cost;
  // 閉路検出用にもう一回更新
  for (int from = 0; from < n; from++) {
    if (cost[from] == INF) {
      continue;
    }
    for (auto e : G[from]) {
      // 更新
      if (cost[e.to] > cost[from] + e.cost) {
        cost[e.to] = cost[from] + e.cost;
      }
    }
  }

  // 始点から到達できるか
  auto can_reach_from_start = can_reach(G, start);
  // 各点が終点へ到達できるか
  auto can_reach_from_goal = can_reach(rev, goal);

  for (int i = 0; i < n; i++) {
    if (can_reach_from_start[i] && can_reach_from_goal[i]) {
      // 始点から終点へ移動できるノードの内、値が更新されるものが存在したら負のループが存在する。
      if (cost_middle[i] != cost[i]) {
        return -INF;
      }
    }
  }

  return cost[goal];
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll n, m, p;
  cin >> n >> m >> p;

  Graph G(n + 1), rev(n + 1);

  rep(i, m) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    G[a].push_back((Edge){b, -c + p});
    rev[b].push_back((Edge){a, -c + p});
  }

  ll ans = bellman_ford(G, rev, 1, n);
  ans *= -1;
  chmax(ans, 0ll);
  if (ans == INF) {
    ans = -1;
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
    string s;
    cin >> s;
    int t = s.size();
    rep(i,t){
        printf("x");
    }
    return 0;
}


Measured memory_bytes: 256
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int n,m,i,j;
            cin>>n>>m;
            ll ar[n+1],ans=0,x,z,ct,y;
            map<ll,ll> mp;
            for(i=1;i<=n;++i)
            {
                cin>>ar[i];
                ++mp[ar[i]];
            }
            vector<int> v;
            for(i=1;i<=m;++i)
            {
                v.clear();
                cin>>x>>z;
                ct=0;
                for(auto it:mp)
                {
                    if(it.f>=z || x==0)
                        break;
                    y=min(x,it.s);
                    ct=ct+y;
                    if(y==it.s)
                    {
                        v.pb(it.f);
                    }
                    else
                    {
                        mp[it.f]-=y;
                    }
                    x=x-y;
                }
                for(auto x:v)
                    mp.erase(x);
                mp[z]+=ct;
            }
            for(auto it:mp)
            {
                ans=ans+it.f*it.s;
            }
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 7936
# coding: utf-8
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
def comb(n, r):  # 組み合わせ
    if n <= 0 or r > n: return 0
    return factorial(n) // factorial(n - r) // factorial(r)

answer = comb(N, 2) + comb(M, 2)
print(answer)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<numeric>
#include<queue>
using namespace std;
using ll = long long;

int main(){
    int n,m;
    cin>>n>>m;
    priority_queue<pair<ll,int>> q;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        q.push(make_pair(a,1));
    }
    for(int i=0;i<m;i++){
        int b,c;
        cin>>b>>c;
        q.push(make_pair(c,b));
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        auto p=q.top();
        q.pop();
        ans+=p.first;
        if(p.second>1){
            p.second--;
            q.push(p);
        }
    }
    cout<<ans<<endl;
} 

Measured memory_bytes: 7352
use std::io;

fn main() {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).unwrap();
    buffer.clear();
    io::stdin().read_line(&mut buffer).unwrap();
    let xs: Vec<i32> = buffer
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    let mut ys = Vec::new();
    for x in xs.into_iter() {
        ys.push(x);
        ys.push(x+1);
        ys.push(x-1);
    }
    ys.sort();
    let mut m = 0;
    let mut prev = &ys[0];
    let mut cnt = 0;
    for i in 0..ys.len() {
        if &ys[i] == prev {
            cnt += 1;
        } else {
            if m < cnt {
                m = cnt
            }
            prev = &ys[i];
            cnt = 1;
        }
    }    
    println!("{}", m);
}



Measured memory_bytes: 8444
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define FOR(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
  int N;
  cin >> N;
  vector<ll> A(N), B(N), C(N);
  FOR(i, N) cin >> A[i];
  FOR(i, N) cin >> B[i];
  FOR(i, N) cin >> C[i];
  sort(all(A));
  sort(all(B));
  sort(all(C));
  ll ans = 0;
  FOR(i, N) {
    auto itr_a = lower_bound(all(A), B[i] );
    auto itr_c = upper_bound(all(C), B[i] );
    ll idx_a = distance(A.begin(), itr_a);
    ll idx_c = C.size() - distance(C.begin(), itr_c);
    ans += idx_a * idx_c;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    int N, M;
    int64_t ans = 0;
    cin >> N >> M;
    vector<pair<int64_t, int64_t>> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i].first >> A[i].second;
    }
    sort(A.begin(), A.end());
    for(int i = 0; i < N; i++) {
        if(M <= A[i].second) {
            ans += A[i].first * M;
            break;
        } else {
            ans += A[i].first * A[i].second;
            M -= A[i].second;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    sort(v.begin(),v.end());
    double ans = v[0];
    for (int i = 1; i < n; ++i) {
        ans = (ans+v[i])/2;
    }
    cout << setprecision(15) << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
//2015
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
int main(void){
	int i,ad[4]={0},e=0,f=0,sum=0;
	for(i=0;i<4;i++){
		cin>>ad[i];
	}
	cin>>e;
	cin>>f;
	sort(ad,ad+4,greater<int>());//降順,昇順＝＝sort(ad,ad+4);
	for(i=0;i<3;i++){
		sum+=ad[i];
	}
	if(e<f){
		sum+=f;
	}
	else{
		sum+=e;
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
string s;int k;
set<string>tt;
int main(){
	std::ios::sync_with_stdio(false);
	cin>>s>>k;
	int len=s.size();
	for(int i=0;i<len;i++){
		string ss="";
		for(int j=i;j<len;j++){
			ss+=s[j];
			tt.insert(ss);
			auto it=tt.end();it--;
			if(tt.size()>k) tt.erase(it);
		}
	}
	auto it=tt.begin();int num=1;
	while(num<k) it++,num++;
	cout<<*it<<endl;
	return 0;
} 

Measured memory_bytes: 256
// #pragma GCC optimize("Ofast")

// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>

using namespace std;

template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}

template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
#define left left228
#define right right228
#define ld long double
#define list list228
// #define prev prev228
#define mp make_pair
#define list list228
#define all(v) v.begin(), v.end()


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int>a(n),b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    int answer = a[0] + b[0];
    while(k--) {
        int x, y, z;
        cin >> x >> y >> z;
        --x;
        --y;
        uin(answer, a[x] + b[y] - z);
    }
    sort(all(a)); sort(all(b));
    uin(answer, a[0] + b[0]);
    cout << answer << '\n';
    return 0;
}

/*
3
1 1 2
2 2 2
3 3 2
2 1 1
3 2 1


2 2
1 1 2
2 2 2
1 2 3
2 1 1

2
2 1 2 2 3
2 2 2 1 1

бархатом обитый гроб
5
1 2
2 3
3 4
3 5
1
2 3
1 2
4 3
2 3 5

*/




Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[2001];
	int i, j;
	
	fgets(str, 2000, stdin);
	
	for (i = 0; i < strlen(str); i++){
		if (strncmp(&str[i], "apple", 5) == 0){
			strncpy(&str[i], "peach", 5);
			continue;
		}
		if (strncmp(&str[i], "peach", 5) == 0){
			strncpy(&str[i], "apple", 5);
		}
	}
	printf("%s", str);
	
	return (0);
}

Measured memory_bytes: 0
// ABC177E.cpp
#include <iostream>
#include <vector>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)

int gcd(int x, int y) {
    if (x % y == 0) {
        return y;
    }
    else {
        return gcd(y, x % y);
    }
}
int main()
{
    int A = 1000006;
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int>count(A);
    rep(i, n) {
        cin >> a.at(i);
        count.at(a.at(i))++;
    }
    bool pairwise = true;
    for (int i = 2; i < A; i++) {
        int cnt = 0;
        for (int j = i; j < A; j += i) {
            cnt += count.at(j);
        }
        if (cnt > 1) pairwise = false;
    }
    if (pairwise) {
        cout << "pairwise coprime" << endl;
        return 0;
    }
    int g = 0;
    rep(i, n) {
        g = gcd(g, a.at(i));
    }
    if (g == 1) {
        cout << "setwise coprime" << endl;
    }
    else {
        cout << "not coprime" << endl;
    }
    return 0;
}


Measured memory_bytes: 10732
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val map = mutableMapOf<String, Int>()
    val n = sc.nextInt()
    for (i in 0 until n) {
        val s = sc.nextLine()
        map[s] = (map[s] ?: 0) + 1
    }
    val m = sc.nextInt()
    for (i in 0 until m) {
        val s = sc.nextLine()
        map[s] = (map[s] ?: 0) - 1
    }
    println(Math.max(0, map.values.max()!!))
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 31396
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using int64 = long long;

void bfs(vector<vector<int64>>& c) {
    queue<int64> q;
    for (int64 i=0; i<10; i++) {
        q.push(i);
        while(!q.empty()) {
            int64 u = q.front(); q.pop();
            for (int64 v=0; v<10; v++) {
                for (int64 j=0; j<10; j++) {
                    if (c[u][v] > c[u][j] + c[j][v]) {
                        c[u][v] = c[u][j] + c[j][v];
                        q.push(v);
                    }
                }
            }
        }
    }
}

int main () {
    int64 h,w;
    cin >> h >> w;
    vector<vector<int64>> c(10, vector<int64>(10));
    for (int64 i=0; i<10; i++) {
        for (int64 j=0; j<10; j++) {
            cin >> c[i][j];
        }
    }

    bfs(c);

    int64 ans = 0;
    for (int64 i=0; i<h; i++){
        for (int64 j=0; j<w; j++) {
            int64 a;
            cin >> a;
            if (a < 0) continue;
            ans +=  c[a][1];
        }
    }

    cout << ans << endl;
}

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

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;

    public void calc()
    {
        cin = new Scanner();
        string S = cin.next();
        Console.WriteLine(dfs(S));
    }

    Dictionary<string, long> dic = new Dictionary<string, long>();

    long dfs(string S)
    {
        if (S == "") return 0;
        if (dic.ContainsKey(S)) return dic[S];
        long ans = 0;
        for (int i = 1; i <= S.Length; i++)
        {
            string NS = S.Substring(0, i);
            string S2 = S.Substring(i, S.Length - i);
            ans += dfs(S2);
            ans += long.Parse(NS) * dfs2(S2);
        }

        return dic[S] = ans;
    }

    Dictionary<string, long> dic2 = new Dictionary<string, long>();
    long dfs2(string S)
    {
        if (S == "") return 1;
        if (dic2.ContainsKey(S)) return dic2[S];
        long ans = 0;
        for (int i = 1; i <= S.Length; i++)
        {
            string NS = S.Substring(0, i);
            string S2 = S.Substring(i, S.Length - i);
            ans += dfs2(S2);
        }
        return dic2[S] = ans;
    }
    

}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        while (i >= s.Length)
        {
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
        }
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Measured memory_bytes: 3160
import sys
A = input()
B = input()
if len(A) < len(B):
    print('LESS')
elif len(A) > len(B):
    print('GREATER')
else:
    for i in range(len(A)):
        if A[i] < B[i]:
            print('LESS')
            sys.exit()
        elif A[i] > B[i]:
            print('GREATER')
            sys.exit()
    print('EQUAL')


Measured memory_bytes: 9012
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, D: "List[int]"):
    tmp = N
    while True:
        i = tmp
        ng = False
        while i > 0:
            if (i % 10) in D:
                ng = True
                break
            i //= 10
        if not ng:
            print(tmp)
            return
        tmp += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    D = [ int(next(tokens)) for _ in range(K) ]  # type: "List[int]"
    solve(N, K, D)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] -= (i+1);
    }
    sort(A.begin(), A.end());
    vector<long long> v(N, 0);
    for (int i = N-1; i >= 0; i--) {
        A[i] -= A[0];
    }
    for (int i = 1; i < N; i++) {
        v[i] = v[i-1] + A[i];
    }
    long long ans = v[N-1];
    for (int i = 1; i < N; i++) {
        long long b = A[i];
        ans = min(ans, -(v[i]-b*(i+1)) + ((v[N-1]-v[i])-b*(N-1-i)));
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
const long long int sMod = 998244353;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int x;
    cin >> x;
    if(x==1) print(0);
    else print(1);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

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

#define MAX_H 500000

void maxHeapify (int *,int);
void buildMaxHeap (int *);
int left (int i){ return i * 2; }
int right (int i){ return i * 2 + 1; }
int h;

int main (void)
{
  int *a,i;

  if (h <= MAX_H)
    scanf ("%d",&h);

  a = malloc(sizeof(int) * h);

  for (i = 1 ; i < h+1 ; i++)
    scanf ("%d",&a[i]);

  buildMaxHeap(a);

  for (i = 1 ; i < h+1 ; i++){
    printf (" %d",a[i]);
  }
  printf ("\n");

  free(a);
  return 0;
}

void maxHeapify (int *a,int i)
{
  int l,r,largest,x;

  l = left(i);
  r = right(i);

  //左の子、自分、右の子で値が最大のnodeを選ぶ
  if (l <= h && a[l] > a[i])
    largest = l;
  else
    largest = i;
  if (r <= h && a[r] > a[largest])
    largest = r;

  if (largest != i){
    //exchange
    x = a[i];
    a[i] = a[largest];
    a[largest] = x;

    maxHeapify(a,largest);
  }

  return;
}

void buildMaxHeap (int *a)
{
  int i;

  for (i = h / 2 ; i >= 1 ; i--)
    maxHeapify(a,i);

  return;
}

Measured memory_bytes: 2472
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int n;
string s;
ll ans = 0;

void solve(ll x,ll y)
{
    if(x==n+1)
    {
        ans += y;
        return;
    }
    ll cur = 0;
    for(ll i=x; i<=n; i++)
    {
        cur = (10*cur) + (s[i]-'0');
        solve(i+1,y+cur);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a+b>c+d)puts("Left");
    else if(a+b==c+d)puts("Balanced");
    else puts("Right");
}


Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
#define INF (1<<29)
typedef struct edge{
  int to,cost;
} edge;

edge* G[100];
int size[100];
int n;
int d[100],v[100],u;
edge e;
int main(){
  int i,j,a,b;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    G[a] = malloc( sizeof( edge ) *b );
    size[a]=b;
    for(j=0;j<b;j++){
      scanf("%d %d",&G[a][j].to,&G[a][j].cost);
    }
    d[i]=INF;
    v[i]=0;
  }
  d[0]=0;
  while(1){
    u=-1;
    for(i=0;i<n;i++){
      if(v[i])continue;
      if(u==-1||d[u]>d[i])u=i;
    }
    if(u==-1)break;
    v[u]=1;
    for(i=0;i<size[u];i++){
      e=G[u][i];
      if(d[e.to]<=d[u]+e.cost)continue;
      d[e.to]=d[u]+e.cost;
    }
  }
  for(i=0;i<n;i++)
    printf("%d %d\n",i,d[i]);
  
  return 0;
}

Measured memory_bytes: 636
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000007;
constexpr int INF = 2000000000;
using namespace std;

typedef pair<int, int> P;
vector<P> v[100001];
int dij(int s, int g) {

	int i;

	priority_queue<P, vector<P>, greater<P> > que;
	bool used[100001] = { false };

	que.push(P(0, s));

	while (!que.empty()) {
		P now = que.top();
		que.pop();

		int cost = now.first;
		int to = now.second;
		used[to] = true;
		if (to == g) {
			return cost;
		}

		for (i = 0; i<v[to].size(); i++) {

			int nextcost = cost + v[to][i].first;
			int next = v[to][i].second;

			if (used[next] == false) {
				que.push(P(nextcost, next));
			}
		}
	}
	return INF;
}

int main() {
	int N, M;
	int a, b, c, d;


	while (cin >> N >> M&&N != 0 && M != 0) {
		for (int i = 0; i < 100000; i++) {
			v[i].erase(v[i].begin(), v[i].end());
		}
		for (int i = 0; i < M; i++) {
			cin >> d;
			if (d == 1) {
				cin >> a >> b >> c;
				a--;
				b--;
				v[a].push_back(P(c, b));
				v[b].push_back(P(c, a));
			}
			else {
				cin >> a >> b;
				a--;
				b--;
				int ans = dij(a, b);
				cout << (ans == INF ? -1:ans) << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 5544
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1000000000000000000;
struct edge{int to,cost,time;};
using P=pair<int,pair<int,int>>;
vector<edge> G[55];
int C[55],T[55],D[55][2600];
signed main(){
  int N,M,S;
  cin>>N>>M>>S;
  while(M--){
    int u,v,a,b;
    cin>>u>>v>>a>>b;
    G[u-1].push_back(edge{v-1,a,b});
    G[v-1].push_back(edge{u-1,a,b});
  }
  for(int i=0;i<N;i++)cin>>C[i]>>T[i];
  for(int i=0;i<N;i++)
    for(int j=0;j<=2500;j++)D[i][j]=INF;
  D[0][min(S,2500LL)]=0;
  priority_queue<P,vector<P>,greater<P>> Q;
  Q.push({0,{0,min(S,2500LL)}});
  while(!Q.empty()){
    P p=Q.top();
    Q.pop();
    for(auto e:G[p.second.first]){
      int m=p.second.second-e.cost;
      if(m>=0 && D[e.to][m]>p.first+e.time){
        D[e.to][m]=p.first+e.time;
        Q.push({p.first+e.time,{e.to,m}});
      }
    }
    int n=min(p.second.second+C[p.second.first],2500LL);
    if(D[p.second.first][n]>p.first+T[p.second.first]){
      D[p.second.first][n]=p.first+T[p.second.first];
      Q.push({p.first+T[p.second.first],{p.second.first,n}});
    }
  }
  for(int i=1;i<N;i++){
    int ans=INF;
    for(int j=0;j<=2500;j++)ans=min(ans,D[i][j]);
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 7368
import java.util.*;

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

    int a = sc.nextInt();
    int b = sc.nextInt();
    
    System.out.println((a + b) % 2 == 1 ? "IMPOSSIBLE" : (a + b) / 2);
  }
}


Measured memory_bytes: 21972
a = int(input())
k =[]
t = 0
for i in range(a):
    k.append(input())
for i in range(a-1):
    if k[i][len(k[i])-1] != k[i+1][0] :
        t = -1
    
if len(k) != len(set(k)):t = -1
if t == -1:
    print("No")
else:
    print("Yes")

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> road(n);
  int a = 0;
  int b = 0;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    road.at(a - 1)++;
    road.at(b - 1)++;
    a = 0;
    b = 0;
  }
  for (int i = 0; i < n; i++) {
    cout << road.at(i) << endl;
  }
}
    
  



Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long


    /// 23 23
    ll pcw[200010],pccw[200010];

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

            ll L,n,tmp;
            vector<ll> cw,ccw;

            cw.pb(0);
            ccw.pb(0);

            cin>>L>>n;

            for(ll i=0;i<n;i++){
                cin>>tmp;
                ccw.pb( tmp );
            }
            for( ll i=ccw.size()-1;i>0;i-- )cw.pb( ccw[i] );

            pccw[0]=ccw[0];
           pcw[n]=L-cw[1]; /// n zato sto smo dodali nulu na pocetak

            for( ll i=1;i<ccw.size();i++ ) pccw [i]=pccw[i-1]+ccw[i];
            for(ll i=cw.size()-2;i>0;i--){
                pcw[i]=pcw[i+1]+L-cw[n+1-i];
            }

            ll res=0;
            for( ll i=0;i<ccw.size()-1;i++ ){
                ll l = i+1, r = ccw.size()-1 ,kraj;
         ///       cout << l << " " << r << "  ee " <<endl;
                if( (r-l+1)%2==0 ){
                    kraj = (l+r+1)/2;
                    ll novi = 2*(pccw[kraj-1] -pccw[l-1]) + 2*pcw[kraj] - (L-cw[n-kraj+1]);
                    res=max( res, novi );
                 //   cout<< res << " "<<novi << " " << l << " " << r << " " << kraj  << " " << pccw[kraj-1] << " " << pcw[kraj] << " " << cw[n-kraj+1] <<endl;
                }
                else{
                    kraj=(l+r)/2;
                    ll novi= 2*( pccw[kraj]-pccw[l-1] )-ccw[kraj] + 2*pcw[kraj+1] ;
                    res=max( res,novi );
                  //  cout<< res << " " << novi << " " << l << " " << r << " " << kraj  << " " << pccw[kraj] << " " << pcw[kraj+1] << " " << ccw[kraj] <<endl;
                }
            }
            /// mislim da je iznad dobro, treba haman isto ponoviti samo kad se krene sa druge strane.
            /// pogubljen sam sa indexima, trebo bi lakse skontati
            ///ovo ispod ne provjerava nulu za drugi smjer, kako sad to dodati?
            for( ll i=ccw.size();i>0;i-- ){
                ll r=i-1,l=1,kraj;
                if( (r-l+1)%2 == 0 ){
                    kraj=(l+r)/2;
                    ll novi = 2*( pcw[kraj+1] - pcw[(r+1)] ) + 2*( pccw[kraj]) - ccw[kraj] ;
              ///      cout<<novi << " aa " <<endl;
               ///     cout << l << " " << r << " " << kraj << " " << pcw[kraj+1] << " " << pcw[r+1] << " " << pccw[kraj]  <<endl;
                    res=max( res,novi );
                }
                else{
                    kraj=(l+r)/2;
                    ll novi = 2*( pcw[kraj] - pcw[r+1] ) - (L-cw[n+1-kraj])  + 2*pccw[kraj-1];
                 ///   cout << novi  << " eeo "<<endl;
                ///    cout << l << " " << r << " " << kraj << " " << pcw[kraj ] << " " << cw[n+1-kraj] << " " << pccw[kraj-1] <<endl;
                    res=max(res,novi);
                }
            }

            cout<<res<<endl;

            return 0;
}































Measured memory_bytes: 6640
/**
 *   author: AK Tiwari
 *   created: 30 January 2019  12:02:38
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
struct vars { ll a,b,c; };
ll i,j,k;
vector< vector< ll > > a(100005, vector< ll >(3));
vector< vector< ll > > cost(100005, vector< ll >(3, 0));

void solve(){
	int n; cin >> n;
	rep(i,0,n-1){
		cin >> a[i][0];
		cin >> a[i][1];
		cin >> a[i][2];
	}
	cost[n-1][0] = a[n-1][0];
	cost[n-1][1] = a[n-1][1];
	cost[n-1][2] = a[n-1][2];

	rrep(i,n-2,0){
		cost[i][0] += max(a[i][0]+cost[i+1][1],a[i][0]+cost[i+1][2]);
		cost[i][1] += max(a[i][1]+cost[i+1][0], a[i][1]+cost[i+1][2]);
		cost[i][2] += max(a[i][2]+cost[i+1][1], a[i][2]+cost[i+1][0]);
	}
	cout<<max( max(cost[0][0], cost[0][1]), cost[0][2] );
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    // ll t;cin>>t;
    // while(t--)
    	solve();
return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define int                 long long
#define FF(i,a,b)           for(int i=a;i<b;i++)
#define BF(i,a,b)           for(int i=a;i>=b;i--)
#define vi                  vector<int>
#define MAP                 map<int,int>
#define pb                  push_back
#define MP                  make_pair
#define F                   first
#define S                   second
#define pi                  pair<int,int>
#define all(v)              v.begin(),v.end()
#define PIE                 3.1415926535897932384626433832795
#define FastIO              ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
//#define ordered_set         tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
/*

    order_of_key (k) : Number of items strictly smaller than k .
    find_by_order(k) : K-th element in a set (counting from zero).

*/
/**************************************************************************************/
                       /*Global Variables*/
const int mod = 1e9+7;
const int N = 2e5+10;
const int inf = 3e18;
vi g[N];
/**************************************************************************************/
template <typename A>istream& operator>>(istream& input,vector<A>& x) {for(auto& i:x)input>>i;return input;}
template<typename A>ostream& operator<<(ostream& output,vector<A>& x) {for(auto& i:x)output<<i<<' ';return output;}
int add(int a, int b){return (a%mod + b%mod + mod)%mod;}
int sub(int a, int b){return (a%mod - b%mod + mod)%mod;}
int mul(int a, int b){return ((a%mod)*(b%mod) + mod)%mod;}
int Power(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}

int dp[1001][1001];

signed main()
{
    FastIO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        vector<string> s(n);
        FF(i,0,n)
        {
            cin>>s[i];
        }
        for(int i=0;i<n;i++)
         if(s[i][0]=='.')
          dp[i][0]=1;
        else break;
        for(int j=0;j<m;j++)
        if(s[0][j]=='.')
        dp[0][j]=1;
        else break;
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                if((i-1)>=0&&s[i-1][j]=='.')
                {
                    dp[i][j]+=dp[i-1][j];
                    dp[i][j]%mod;
                }
                if((j-1)>=0&&s[i][j-1]=='.')
                {
                    dp[i][j]+=dp[i][j-1];
                    dp[i][j]%=mod;
                }
            }
        }
        cout<<dp[n-1][m-1]<<"\n";


    }

}
/*
|| Do what you can with all you have,wherever you are. ||

|| Knowing is not enough, we must apply. Wishing is not enough, we must do. ||

|| A goal is a dream with deadline. ||

|| Whether you think you can or you think you can't, you're right. ||

|| A year from now you may wish you had started today ||
*/



Measured memory_bytes: 13824
import sys
a = int(input())
numlist = [a]
for i in range(2,500):
    if a % 2 ==0:
        a //= 2
        numlist.append(a)
    else:
        a = a*3 + 1
        numlist.append(a)

kind = {}
count = 0
for s in numlist:
    count += 1
    if s in kind:
        print(count)
        sys.exit()
    else:
        kind[s] = 1

Measured memory_bytes: 3064
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<assert.h>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>
using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> P1;
typedef long long int ll;

//define
#define INF 1e9
#define NUM 1000000007
#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))


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

	if (n == 7 || n == 5 || n == 3) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define maxn 100020
#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define pb push_back
#define prev prev_
#define stack stack_
#define inf 0x3f3f3f3f

int n,ans;

int main(){
	cin>>n;
	rep(i,1,n){
		if ( !(i & 1) ) continue;
		int cnt = 0;
		rep(j,1,i){
			if ( (i % j) == 0 ) cnt++;
		}
		if ( cnt == 8 ) ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,n) for(int i=1; i<=(n); i++)

int main() {
	int n,m,ans=1;
	string s;
    cin>>s;
    n=s.size();
    rep(i,(n-1)/2){
        if(s[i]!=s[n-1-i])ans=0;
    }
    rep(j,(n+1)/4){
        if(s[j]!=s[(n+1)/2+j])ans=0;
    }
    if(ans)cout<<"Yes";
    else cout<<"No";
	return 0;
}



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

int main(void)
{
	int n;
	cin >> n;

	int w;
	cin >> w;

	vector<int> wt;
	vector<int> val;
	for(int i = 0;i < n;i++)
	{
		int u;
		cin >> u;
		wt.push_back(u);
		cin >> u;
		val.push_back(u);
	}

	long long int dp[n+1][w+1];
	memset(dp,0,sizeof(dp));


	for(int i = 0;i <= n;i++)
	{
		for(int j = 0;j <= w;j++)
		{
			if(i == 0 || j == 0)
				dp[i][j] = 0;
			else if(wt[i-1] > j)
				dp[i][j] = dp[i-1][j];
			else
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-wt[i-1]] + val[i-1]);
		}
	}

	cout << dp[n][w];

	return 0;
}

Measured memory_bytes: 79104
program small_products
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer :: n, k, m, i, j
  integer(8) :: dp(100,70000), s
  dp = 0_8
  read(*,*) n, k
  m = floor(sqrt(real(n,8)))
  if (m*(m+1).gt.n) then
    m = 2*m-1
  else
    m = 2*m
  end if
  do j = 1, m
    dp(1,j) = int(max(1,n/(m-j+1)-n/(m-j+2)),8)
  end do
  do i = 2, k
    s = 0_8
    do j = m, 1, -1
      s = mod(s+dp(i-1,m-j+1),md)
      dp(i,j) = s*dp(1,j)
    end do
  end do
  write(*,'(i0)') mod(sum(dp(k,1:m)),md)
  stop
end program small_products

Measured memory_bytes: 54912
# coding: utf-8
class Case02

  def initialize
  end

  def show
    p self.instance_variables
        .map{ |sym| [sym, self.instance_variable_get(sym)] }
        .to_h
  end
  
  # 実行する
  def execute
    read
    solve
    output
  end

  # 読込
  def read
    @n = gets.chomp.to_i
    @xu = []
    @n.times do
      x, u = gets.chomp.split
      @xu << [x.to_f, u]
    end
  end

  # 回答
  def solve
    @result = @xu.reduce(0.0) do |tmp, e|
      if e[1] == 'JPY'
        tmp + e[0] 
      else
        tmp + e[0] * 380000.0 
      end
    end
    # tmp = 0.0
    # @xu.each do |e|
    #   if e[1] == 'JPY' then
    #     tmp += e[0] 
    #   else
    #     tmp += e[0] * 380000.0
    #   end
    # end
    # @result = tmp
  end
  
  # 出力
  def output
    puts @result
  end

end

# 
Case02.new.execute if $0 == __FILE__



Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define SZ(x) ((int)(x).size())
#define MEM(x,a) memset(x,a,sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
const ll mod=1000000007,N=1e5+5,M=1e5+5,INF=0x3f3f3f3f;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//head

int main(void){
    int n,m;
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2;
    return 0;
}

Measured memory_bytes: 256
l = []
while(True):
    x = (list(map(int,input().split())))
    if x[0] == 0 and x[1] == 0:
        break
    
    l.append(x)

cnt = 0
ln = len(l)

while(cnt < ln):
    H = l[cnt][0]
    W = l[cnt][1]
    
    for i in range(H):
        for j in range(W):
            if i == 0 or i == H-1:
                print("#", end = "")
            
            elif j == 0 or j == W-1:
                print("#", end = "")
            
            else:
                print(".", end = "")
        
        print()
    
    print()
            
    cnt += 1


Measured memory_bytes: 7012
#include<stdio.h>
 
#define N 100000
 
int bserch(int a[], int b, int key){
  int i,left =0, right =b;
 
  while(left < right){
    i = (left+right)/2;
    if(a[i] == key){
      return 1;
    }
    else if(key < a[i]){
      right = i;
    }
    else{
      left = i +1;
    }
  }
  return 0;
}
 
int main(){
  int n, q, i, j, count = 0, discount = 0;
  int S[N],T[N];
   
   scanf("%d",&n);
   
  for(i=0; i<=n-1;i++){
    scanf("%d",&S[i]);
  }
 
  scanf("%d",&q);
 
  for(i=0;i<=q-1;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<=q-1;i++){
    if(bserch(S,n,T[i]) == 1){
      count += 1;
    }
  }
 
  printf("%d\n", count);
   
   
  return 0;
}

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

const char NL = '\n';
const int MOD = 1e9 + 7;

void solve()
{
    int n; cin >> n;
    vector<int> v;
    unordered_set<int> used;
    for (int i = 0; i < n; ++i) {
        int val; cin >> val;
        if (used.find(val) == used.end()) {
            v.push_back(val);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                int a = v[i], b = v[j], c = v[k];
                if (a != b && b != c && a != c && a + b > c && b + c > a && a + c > b) ++ans;
            }
        }
    }
    cout << ans << NL;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 3640
//This is getting accepted!
#include<bits/stdc++.h>
#define ll long long
#define oo 1000000009

using namespace std;

const int MOD = 1000000007;
const double EPS = 1e-8;
const double PI = 2 * acos(0);
const int MAXN = 1e5 + 6;

struct Node {
	int b, u, l;
};

Node node[MAXN];
ll cumu[MAXN];
int n;
ll X;
ll losing;

bool cmp(Node u, Node v) {
	return (1ll * u.u * (X-u.b)) + (1ll * u.l *(u.b)) > (1ll * v.u * (X-v.b)) + (1ll * v.l *(v.b));
}


bool input() {
	n = 0; losing = 0;
	cin >> n >> X;
	
	for (int i = 1; i <= n; ++i) {
		cin >> node[i].b >> node[i].l >> node[i]. u;
		losing += 1ll * node[i].b * node[i].l;
	}
	
	return !cin.fail();
}

bool isok(ll nhour) {
	int e = nhour / X;
	if (e == n) return 1;
	
	ll total = cumu[e];
	
	for (int i = 1; i <= n; ++i) {
		ll tmp = total;
		if (i <= e) {
			tmp -= (1ll * node[i].l * node[i].b + 1ll * node[i].u * (X-node[i].b));
			tmp += (1ll * node[e+1].l * node[e+1].b + 1ll * node[e+1].u * (X-node[e+1].b));
		}
		
		tmp += min((nhour%X), (ll)node[i].b) * 1ll * node[i].l + max(0ll, nhour%X - node[i].b) * 1ll * node[i].u;
		if (tmp >= losing) return 1;
	}
	
	return 0;
}

void process() {
	sort(node + 1, node + n + 1, cmp);
	for (int i = 1; i <= n; ++i) {
		cumu[i] = cumu[i-1] + 1ll * node[i].l * node[i].b + 1ll * node[i].u * (X-node[i].b);
	}
	
	ll l = 0, r = 1ll * n * X, mid;
//	ll l = 0, r = (ll) 10, mid;
	while (l < r) {
		mid = (l+r)/2;
		if (isok(mid)) {
			r = mid;
		}
		else
			l = mid+1;
	}
	
	cout << l << endl;
	
}

int main(){
    #ifndef ONLINE_JUDGE
//    freopen("../out.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    	
	while(input()) {
		process();
	}
	
    return 0;

}


Measured memory_bytes: 2176
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1#隣接グラフを作成
visited=[0]*n#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(dfs(0,visited,n))


Measured memory_bytes: 3064
fun main(args: Array<String>) {
  val N = readInt()
  val AN = readInts()

  val dp = Array(N + 1) { 0 }
  for (i in AN.indices) {
    dp[AN[i]]++
  }

  fun comb(n: Int): Long {
    return n.toLong() * (n - 1) / 2
  }

  var sum = 0L
  for (i in dp.indices) {
    if (dp[i] > 1) sum += comb(dp[i])
  }
  for (i in AN.indices) {
    val it = AN[i]
    val d = comb(dp[it]) - comb(dp[it] - 1)
    println(sum - d)
  }
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }
fun readLong() = readString().toLong()
fun readLongs() = readStrings().map { it.toLong() }


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

int main(){
  int N, x;
  cin >> N >> x;
  vector<int> ans(2*N-1);
  if(x < 2 or x == 2*N-1){
    cout << "No" << endl;
    return 0;
  }
  int m = (2*N-1)/2;
  ans[m] = x;
  ans[m-1] = 2*N-1;
  ans[m+1] = 1;
  int l = 2, r = 2*N-2;
  for(int i = 0; i < m-1; ++i){
    if(l == x) ++l;
    if(r == x) --r;
    ans[i] = l;
    ans[m+2+i] = r;
    --r;
    ++l;
  }
  cout << "Yes" << endl;
  for(int i = 0; i < 2*N-1; ++i) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 2304
import java.util.*;

 class Main
 {
   public static void main(String args[])
   { 
    input();
   }
   static void input()
   {
     Scanner sc = new Scanner(System.in);
     
     int w = sc.nextInt();
     
     int h = sc.nextInt();
     
     int x = sc.nextInt();
     
     int y = sc.nextInt();
     
     int r = sc.nextInt();
     
     coordinate(w,h,x,y,r);
   }
   static void coordinate(int w,int h,int x,int y,int r)
   {//X-axis judgment
     if(x - r < 0 || x + r > w)
     {
       System.out.println("No");
       
       return ;
     }
     if(y - r < 0 || y + r > h)
     {
       System.out.println("No");
       
       return ;
     }
     else System.out.println("Yes");
     
     return ;
   }
 }
    


Measured memory_bytes: 26320