akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define vite ios_base::sync_with_stdio(false); cin.tie(NULL);
int main()
{
    vite;
    string s, l;
    int t = 0;
    cin >> s >> l;
    for (int i = 0; i < s.size();i++)
    {
        if(s[i]==l[i])
            t++;
    }
    if(t==s.size())
        cout << "Yes";
    else
    {
        cout << "No";
    }
    
    return 0;
}

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

int main() {
  int N,ans=0;
  cin>>N;
  vector<int> D(N),E(N);
  for(int i=0 ;i<N;i++){
    cin>>D.at(i)>>E.at(i);
  }
  for(int i=0;i<N-2;i++){
    if(D.at(i) == E.at(i) && D.at(i+1) == E.at(i+1) && D.at(i+2)==E.at(i+2)){
      cout<<"Yes"<<endl;
      ans=1;
      break;
    }
  }
  if(ans==0)
    cout<<"No"<<endl;
}


Measured memory_bytes: 3628
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
	"sort"
)

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

type action struct {
	b int
	c int
}

type actions []action

func (a actions) Len() int           { return len(a) }
func (a actions) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a actions) Less(i, j int) bool { return a[i].c > a[j].c }

func main() {
	sc.Split(bufio.ScanWords)

	n, m := scanInt(), scanInt()
	a := make(actions,n)
	for i := 0; i < n; i++ {
		a[i].c = scanInt()
		a[i].b = 1
	}

	bc := make(actions, m)
	for i := 0; i < m; i++ {
		bc[i].b = scanInt()
		bc[i].c = scanInt()
	}

	bc = append(bc,a...)

	sort.Sort(bc)

	ans := int64(0)
	num := 0
	for _, e := range bc {
		if num == n {
			break
		}
		for ;e.b!=0; {
			if num == n {
				break
			}
			ans += int64(e.c)
			num++
			e.b--
		}
	}

	fmt.Println(ans)

}


Measured memory_bytes: 9600
import java.io.*;
import java.util.*;
import java.math.*;

class Main{	
		public static void  calc_tre(ArrayList<Double> a){
			double d,an = 0;
			double x=0,y=0,now_an=0;
			
			for(int i=0;i<a.size()/2;i++){
				d = a.get(i*2);
				an = a.get(i*2+1);
				
				x += d * Math.sin(Math.toRadians(now_an));
				y += d * Math.cos(Math.toRadians(now_an));
				now_an += an;
			}
			
			System.out.print((int)x + "\n" + (int)y + "\n");
		}
		
		public static void main(String args[]) throws IOException{
			String str;
			double n1,n2;
			ArrayList<Double> inp = new ArrayList<Double>();
			Scanner scan = new Scanner(System.in);
			
			while(scan.hasNext()){
				str = scan.next();
				String[] strAry = str.split(",");
				n1 = Double.parseDouble(strAry[0]);
				n2 = Double.parseDouble(strAry[1]);
				inp.add(n1);
				inp.add(n2);
			}
			calc_tre(inp);

	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAX=200020;
int n,a[MAX];
ll s;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]),a[i]-=i;
    sort(a,a+n);
    for(int i=0;i<n;i++) s+=(ll)abs(a[n/2]-a[i]);
    printf("%lld\n",s);
}


Measured memory_bytes: 1024
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
ans=0

for i in range(n-1):
    if a[i]+1==a[i+1]:
        ans+=c[a[i]-1]
print(ans+sum(b))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	lli A,B,C;
	cin>>A>>B>>C;
	if(A==B&&B==C&&A%2==0){
      cout<<-1<<endl;
      return 0;
    }
	lli ans=0;
	while(true){
		if(A%2!=0||B%2!=0||C%2!=0)break;
		ans++;
		lli X=A/2,Y=B/2,Z=C/2;
		A=Y+Z;
		B=Z+X;
       	C=X+Y;
	}
	cout<<ans<<endl;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct edge {
  ll to, cost;
};

int main() {
  ll N; cin >> N;
  ll X, M; cin >> X >> M;
  ll S = 0; // 最終的に答えとなる和
  vector<P> memo(M); // その値Xが { 何番目に出現したか, それまでの計算結果(和) }
  for(ll i = 0; i < N; ++i) {
    if(memo[X].first) { // もしその値がすでに配列にあれば、ループ最後の回りきらないフェーズまでワープさせる
      // 今の順番と、かつてXが出てきた番号の差。これが、ループ1周分の長さになる
      const auto t = i - memo[X].first;
      // この時点で、あとループを何周するか？
      const auto c = (N - i - 1) / t;
      // ループ1周分の長さ * ループを回る回数 をiに足し込む
      i += t * c;
      // ループ1周分の和(累積和っぽく求める) * ループを回る回数 をSに足し込む
      S += (S - memo[X].second) * c;
    } else { // もし配列にまだXが無ければ
      memo[X] = P(i, S); // 配列のX番目にpairを格納する。
    }
    // 必ずSとXを更新する
    S += X; (X *= X) %= M;
  }
  cout << S << endl;
}

Measured memory_bytes: 4848
-- ITP1_2_C
-- Lemmas -------------------------
intstostrs :: [Integer] -> [String]
intstostrs xs = map show xs
strstoints :: [String] -> [Integer]
strstoints xs =  map read xs
iotoints input = (strstoints (words input))
intstoioLn output = putStrLn $ unwords $ intstostrs output 
-- -------------------------------

qsort :: [Integer] -> [Integer]
qsort [] = []
qsort (piv:xs) = qsort smaller ++ [piv] ++ qsort larger
    where
      smaller = [x | x <- xs, x <= piv ]
      larger = [x | x <- xs, piv < x]

main = do
  str <- getLine
  intstoioLn $ qsort $ iotoints str

Measured memory_bytes: 3656
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	s := make([]int, n)
	m := map[int]int{}
	for i := 0; i < n; i++ {
		num := nextInt()
		s[i] = num
		m[num]++
	}

	base := 0
	for _, v := range m {
		base += v * (v - 1) / 2
	}

	for i := 0; i < n; i++ {
		ans := base
		num, ok := m[s[i]]
		if !ok {
			panic("error")
		}
		ans -= num * (num - 1) / 2
		ans += (num - 1) * (num - 2) / 2
		fmt.Println(ans)
	}
}


Measured memory_bytes: 15416
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;

const int INF = (int)1e8;
typedef pair<int, int> P;

int main() {
  while(true) {
    int W, H; cin >> W >> H;
    if(W == 0 && H == 0) break;
    bool wall[H][W][4];
    const int dx[4] = { 1, 0, -1, 0 };
    const int dy[4] = { 0, -1, 0, 1 };
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        wall[i][j][0] = false;
        wall[i][j][1] = false;
        wall[i][j][2] = false;
        wall[i][j][3] = false;
        if(i == 0) wall[i][j][1] = true;
        if(i == H - 1) wall[i][j][3] = true;
        if(j == 0) wall[i][j][2] = true;
        if(j == W - 1) wall[i][j][0] = true;
      }
    }
    for(int i = 0 ; i < H; i++) {
      for(int j = 0; j < W - 1; j++) {
        int s; cin >> s;
        if(s) {
          wall[i][j][0] = true;
          wall[i][j+1][2] = true;
        }
      }
      if(i != H - 1) {
        for(int j = 0; j < W; j++) {
          int s; cin >> s;
          if(s) {
            wall[i][j][3] = true;
            wall[i+1][j][1] = true;
          }
        }
      }
    }

    int d[H][W];
    for(int i = 0; i < H; i++)
      for(int j = 0; j < W; j++) d[i][j] = INF;
    queue<P> Q;
    Q.push(P(0, 0));
    d[0][0] = 1;
    while(!Q.empty()) {
      P p = Q.front(); Q.pop();
      for(int i = 0; i < 4; i++) {
        int ny = p.first + dy[i];
        int nx = p.second + dx[i];
        if(0 <= ny && ny < H && 0 <= nx && nx < W && d[ny][nx] == INF && wall[p.first][p.second][i] == 0) {
          d[ny][nx] = d[p.first][p.second] + 1;
          Q.push(P(ny, nx));
        }
      }
    }
    if(d[H-1][W-1] != INF) {
      cout << d[H-1][W-1] << endl;
    }
    else {
      cout << 0 << endl;
    }
  }
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  int x;
  cin>>x;
  if(x<1200){
    cout<<"ABC"<<endl;
  }else{
    cout<<"ARC"<<endl;
  }
  return 0;
}


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


template <typename T> using Distance = std::vector<std::vector<T>>;
constexpr int INF = 100000000;


template <typename T> void in_place_init_dist(int num_vertices, Distance<T>& dist) {
	for (auto i = 0; i < num_vertices; i++) {
		for (auto j = 0; j < num_vertices; j++)
		{
			if (i == j)
			{
				dist[i][j] = 0;
			}
			else
			{
				dist[i][j] = INF;
			}
		}
	}
}


template <typename T> void in_place_warshall_floyd(int num_vertices, Distance<T>& dist) {
	for (auto k = 0; k < num_vertices; k++)
	{
		for (auto i = 0; i < num_vertices; i++)
		{
			for (auto j = 0; j < num_vertices; j++)
			{
				dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
}


int main() {
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	while (true)
	{
		int n, m;
		std::cin >> n >> m;
		if (n == 0 && m == 0)
		{
			break;
		}
		Distance<int> cost;
		Distance<int> time;
		cost = Distance<int>(m, std::vector<int>(m, 0));
		time = Distance<int>(m, std::vector<int>(m, 0));
		in_place_init_dist(m, cost);
		in_place_init_dist(m, time);
		int a, b, c, t;
		for (auto i = 0; i < n; i++)
		{
			std::cin >> a >> b >> c >> t;
			a--;
			b--;
			cost[a][b] = c;
			cost[b][a] = c;
			time[a][b] = t;
			time[b][a] = t;
		}
		in_place_warshall_floyd(m, cost);
		in_place_warshall_floyd(m, time);
		int k, p, q, r;
		std::cin >> k;
		for (auto i = 0; i < k; i++)
		{
			std::cin >> p >> q >> r;
			p--;
			q--;
			std::cout << (r == 0 ? cost[p][q] : time[p][q]) << std::endl;
		}
	}

	return EXIT_SUCCESS;
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const ll INF = 1e18;
const int inf = 1e8;


void solve()
{
  string S;
  cin >> S;
  S[3]='8';
  cout << S << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
using ll = long long;
using itn = int;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll dp[100010];

int main() {

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

    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    for (int i = 0; i < 100010; i++) {
        dp[i] = INF;
    }

    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            
            chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
            // if (i-j >= 0) chmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
        }
    }

    cout << dp[n-1] << endl;

    return 0;
}

Measured memory_bytes: 1408
//abc119_d.cpp
//Sun Jun  2 14:03:10 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int a,b,q;
	cin >> a >> b >> q;

	set<ll> s;
	s.insert(-1000000000000000000);
	s.insert(1000000000000000000);
	for (int i=0;i<a;i++){
		ll temp;
		cin >> temp;
		s.insert(temp);
	}

	set<ll> t;
	t.insert(-1000000000000000000);
	t.insert(1000000000000000000);
	for (int i=0;i<b;i++){
		ll temp;
		cin >> temp;
		t.insert(temp);
	}

	ll x[q];
	for (int i=0;i<q;i++){
		cin >> x[i];
		auto itr = s.lower_bound(x[i]);
		ll shrine_right = *itr;
		itr--;
		ll shrine_left = *itr;
		auto itr2 = t.lower_bound(x[i]);
		ll temple_right = *itr2;
		itr2--;
		ll temple_left = *itr2;

		ll ans = 9000000000000000000;
		ans = min(ans,abs(x[i]-shrine_left)+abs(shrine_left-temple_left));
		ans = min(ans,abs(x[i]-shrine_left)+abs(shrine_left-temple_right));
		ans = min(ans,abs(x[i]-temple_left)+abs(temple_left-shrine_left));
		ans = min(ans,abs(x[i]-temple_left)+abs(temple_left-shrine_right));
		ans = min(ans,abs(x[i]-shrine_right)+abs(shrine_right-temple_left));
		ans = min(ans,abs(x[i]-shrine_right)+abs(shrine_right-temple_right));
		ans = min(ans,abs(x[i]-temple_right)+abs(temple_right-shrine_left));
		ans = min(ans,abs(x[i]-temple_right)+abs(temple_right-shrine_right));

		cout << ans << endl;
	}


//	printf("%.4f\n",ans);
}

Measured memory_bytes: 11520
S=input()
n=len(S)
total=0
for i in range(2**(n-1)):
  t=0
  for j in range(n):
    t*=10
    t+=int(S[j])
    if ((i>>j)&1):
      total+=t
      t=0
  total+=t
  
print(total)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
ll dp[4000][4000];
int main() {
  string s,t;
  cin >> s >> t;
  int n = sz(s), m = sz(t);
  rep(i,n){
    rep(j,m){
      if(s[i] == t[j]){
        dp[i+1][j+1] =dp[i][j]+1; 
      }
      else{
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
      }
    }
  }
  string ans = "";
  int x = n, y = m;
  while(x > 0 && y > 0){
    if(dp[x][y] == dp[x-1][y]) x--;
    else if(dp[x][y] == dp[x][y-1]) y--;
    else{
      ans.push_back(s[x-1]);
      x--;
      y--;
    }
  }
  reverse(rng(ans));
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 94208
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N,D1,D2;
vector<int> G[600 * 600 + 5];
int viz[600 * 600 + 5];
int type[600 * 600 + 5];

int hsh(int x,int y){
    return x * 2 * N + y;
}

void build(int D){
    for(int i = 0;i < 600 * 600 + 5;i++){
        G[i].clear();
        viz[i] = 0;
    }

    for(int s = 0;s <= 2 * N;s++){
        if(D < 1LL * s * s){
            continue;
        }
        int t = sqrt(D - 1LL * s * s);
        if(1LL * t * t + 1LL * s * s != D){
            continue;
        }
        for(int x = 0;x < 2 * N - s;x++){
            for(int y = 0;y < 2 * N - t;y++){
                G[hsh(x,y)].push_back(hsh(x + s,y + t));
                G[hsh(x + s,y + t)].push_back(hsh(x,y));
            }
            for(int y = 2 * N - 1;y >= t;y--){
                G[hsh(x,y)].push_back(hsh(x + s,y - t));
                G[hsh(x + s,y - t)].push_back(hsh(x,y));
            }
        }
        for(int x = 2 * N - 1;x >= s;x--){
            for(int y = 0;y < 2 * N - t;y++){
                G[hsh(x,y)].push_back(hsh(x - s,y + t));
                G[hsh(x - s,y + t)].push_back(hsh(x,y));
            }
            for(int y = 2 * N - 1;y >= t;y--){
                G[hsh(x,y)].push_back(hsh(x - s,y - t));
                G[hsh(x - s,y - t)].push_back(hsh(x,y));
            }
        }
    }
}

void mark(int shift){
    for(int x = 0;x < 2 * N;x++){
        for(int y = 0;y < 2 * N;y++){
            if(!viz[hsh(x,y)]){
                queue<pair<pair<int,int>,int> > Q;
                Q.push({{x,y},1});
                viz[hsh(x,y)] = 1;
                type[hsh(x,y)] |= 1 << shift;
                while(!Q.empty()){
                    int x = Q.front().first.first;
                    int y = Q.front().first.second;
                    int part = Q.front().second;
                    Q.pop();
                    for(auto it:G[hsh(x,y)]){
                        if(!viz[it]){
                            viz[it] = 1;
                            type[it] |= (!part) << shift;
                            Q.push({{it / (2 * N),it % (2 * N)},!part});
                        }
                    }
                }
            }
        }
    }
}

vector<pair<int,int> > fr[4];

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

    build(D1);
    mark(0);
    build(D2);
    mark(1);

    for(int x = 0;x < 2 * N;x++){
        for(int y = 0;y < 2 * N;y++){
            fr[type[hsh(x,y)]].push_back({x,y});
        }
    }

    for(int k = 0;k < 4;k++){
        if(fr[k].size() >= N * N){
            int num = N * N;
            for(auto it:fr[k]){
                cout << it.first << " " << it.second << "\n";
                num--;
                if(!num){
                    return 0;
                }
            }
        }
    }

    return 0;
}


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

long long keisan(long long n){
  return n*(n-1)/2;
}
int main()
{
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    a[i]--;
  }
  vector<int>kazu(n);
  for(int i=0;i<n;i++){
    kazu[a[i]]++;
  }
  long long sum=0;
  for(int i=0;i<n;i++){
    sum+=keisan(kazu[i]);
  }
  for(int i=0;i<n;i++){
    long long kotae=sum;
    kotae-=keisan(kazu[a[i]]);
    kotae+=keisan(kazu[a[i]]-1);
    cout<<kotae<<endl;
  }
  return 0;
}

Measured memory_bytes: 4096
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int mod = 998244353;

int a[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n;
  cin>>n;
  int ret = 0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    ret^=a[i];
  }
  for(int i=0;i<n;i++){
    cout<<(ret^a[i]);
    if(i==n-1)cout<<endl;
    else cout<<" ";
  }
  return 0;
}

Measured memory_bytes: 4300
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    int a = x, b = y, c = z;
    swap(a,b);
    swap(a,c);
    cout << a << " " << b << " " << c << endl;
    return 0;
}

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

int N,K,X,Y,sum;//KはくまでX円でNはくする

int main(){

	cin>>N>>K>>X>>Y;
	if(N>K){
		sum=K*X+(N-K)*Y;
	}
	else{sum=X*N;}
	

	cout<< sum<<endl;
	return 0;

	}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
long long dp[105][100005];
int main(){
  long long n,W,V=0,ans=0,w[105],v[105],v1=0;
  cin>>n>>W;
  for(int i=0;i<n;i++){
    cin>>w[i]>>v[i];
    V+=v[i];
  }
  for(int i=1;i<=V;i++){
    dp[0][i]=10000000000ll;
  }
  v1=v[0];
  for(int i=0;i<n;i++){
    for(int j=0;j<=V;j++){
      if(v[i]<=j){
	dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
      }
      else
	dp[i+1][j]=dp[i][j];
    }
  }
  for(int j=0;j<=V;j++){
    if(ans<=j && dp[n][j]<=W)
      ans=j;
  }
  cout<<ans<<endl;
      return(0);
}


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

int main(){
        int a,b,h,m;
        cin >> a >> b >> h >> m;
        double r,c;
        double pi = 3.141592653589793238;
        r=fabs(2*pi*abs((h*30+0.5*m-m*6)/360));
        c=sqrt(a*a+b*b-2*a*b*cos(r));
        cout << setprecision(20) << c << endl;
}

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

int main() {
  int N; cin >> N;
  int cnt = 0;
  vector<int> A(N);
  vector<int> B(N);
  
  for(int i=0; i<N; i++){
    cin >> A[i]; //ch
    B[i] = A[i];
  }
  
  sort(B.begin(),B.end());
  
  for(int i=0; i<N; i++){
    if(A[i] != B[i]){
      cnt++;
    }
  }
  
  if(cnt <= 2){
    cout << "YES" << endl;
  }
  else{cout << "NO" << endl;
      }
}
      

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i< (int) n; i++)
 
 
int main() {
     string S;
     cin >> S;

     string tango[4] = {"dream","dreamer","erase","eraser"};

     reverse(S.begin(), S.end());
     rep(i,4){reverse(tango[i].begin(),tango[i].end());}


    for (int i = 0; i < S.size();){
        bool can2 = false ;
        rep(j,4){
            string d = tango[j];
            if(S.substr(i,d.size()) ==d){
                can2 = true;
                i += d.size();
            }
        }
        if(!can2){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    }


    


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

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

int a, p;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>a>>p;
	p += a*3;

	cout<<p/2;

	return 0;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter, defaultdict
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n, *a = map(int, read().split())
counter = list(Counter(a).items())
cnt = defaultdict(int)
memo = defaultdict(int)
for k, v in counter:
    if v > 1:
        cnt[k] = cmb(v, 2)
        if v > 2:
            memo[k] = cmb(v - 1, 2)
        else:
            memo[k] = 0
    else:
        cnt[k] = 0
        memo[k] = 0
ans = sum(cnt.values())
for aa in a:
    print(ans - cnt[aa] + memo[aa])


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

int main() {
  int A,B,l=0;
  cin>>A>>B;
  for(int i=0;i<B-A+1;i++){
    int a=(A+i)/10000;
    int b=(A+i-a*10000)/1000;
    int c=(A+i)%10;
    int d=((A+i-c)/10)%10;
    if((a==c) & (b==d)){
      l+=1;
    }
    else{
      l+=0;
    }
  }
  cout << l <<endl;
}

Measured memory_bytes: 256
from sys import stdin

n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
B = [int(x) for x in stdin.readline().rstrip().split()]
C = [int(x) for x in stdin.readline().rstrip().split()]

ans = sum(B)

for i in range(n-1):
    if A[i+1] == A[i] + 1:
        ans += C[A[i]-1]

print(ans)

Measured memory_bytes: 9192
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main d = new Main();
        long[] answer = d.solve();
        int M = answer.length;
        for (int i = 0; i < M; i++) {
            System.out.println(answer[M - 1 - i]);
        }
    }

    public long[] solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        List<String> edge_list = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            A[i] = scan.nextInt() - 1;
            B[i] = scan.nextInt() - 1;
        }
        UnionFind union_find = new UnionFind(N);
        long[] answer = new long[M];
        long current_answer = new BigInteger(Integer.toString(N)).multiply(new BigInteger(Integer.toString(N - 1))).divide(new BigInteger("2")).longValue();
        int i = 0;
        do {
            answer[i] = current_answer;
            int a_parent = union_find.find(A[M - 1 - i]);
            int b_parent = union_find.find(B[M - 1 - i]);
            if (a_parent != b_parent) {
                current_answer = current_answer - union_find.size(a_parent) * union_find.size(b_parent);
            }
            union_find.unite(A[M - 1 - i], B[M - 1 - i]);
            i += 1;
        } while (i < M);
        return answer;
    }

    class UnionFind {
        private int[] parent = null;
        private int[] rank = null;
        private int[] size = null;
        public UnionFind(int N) {
            int[] parent = new int[N];
            int[] rank = new int[N];
            int[] size = new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }
            this.parent = parent;
            this.rank = rank;
            this.size = size;
        }

        public int size(int x) {
            int parent = this.find(x);
            return this.size[parent];
        }
        public void unite(int x, int y) {
            x = this.find(x);
            y = this.find(y);
            if (x == y) {
                return;
            }
            int size_x = this.size[x];
            int size_y = this.size[y];
            this.size[y] += size_x;
            this.size[x] += size_y;
            if (this.rank[x] < this.rank[y]) {
                this.parent[x] = y;
                return;
            }
            this.parent[y] = x;
            if (this.rank[x] == this.rank[y]) {
                this.rank[x] += 1;
            }
        }

        public int find(int x) {
            if (this.parent[x] == x) {
                return x;
            }
            return this.parent[x] = find(this.parent[x]);
        }

        public boolean same(int x, int y) {
            return find(x) == find(y);
        }
    }
}


Measured memory_bytes: 93000
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

//scc
const int MAX_V=1e5+1;
int V;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from,int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v){
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    if(!used[G[v][i]])dfs(G[v][i]);
  }
  vs.push_back(v);
}

void rdfs(int v,int k){
  used[v]=true;
  cmp[v]=k;
  for(int i=0;i<rG[v].size();i++){
    if(!used[rG[v][i]])rdfs(rG[v][i],k);
  }
}

int scc(){
  memset(used,0,sizeof(used));
  vs.clear();
  for(int v=0;v<V;v++){
    if(!used[v])dfs(v);
  }
  memset(used,0,sizeof(used));
  int k=0;
  for(int i=vs.size()-1;i>=0;i--){
    if(!used[vs[i]])rdfs(vs[i],k++);
  }
  return k;
}

signed main(){
  int n;
  cin>>V>>n;
  vector<int> s(n),d(n);
  for(int i=0;i<n;i++){
    cin>>s[i]>>d[i];
    s[i]--;
    d[i]--;
    add_edge(s[i],d[i]);
  }

  int sz=scc();

  vector<vector<int> > dag(sz),rdag(sz);
  for(int i=0;i<n;i++){
    if(cmp[s[i]]!=cmp[d[i]]){
      dag[cmp[s[i]]].push_back(cmp[d[i]]);
      rdag[cmp[d[i]]].push_back(cmp[s[i]]);
    }
  }

  int ans=1;
  vector<vector<int> > dp(sz,vector<int>(2,1));
  for(int i=0;i<sz;i++){
    for(int j=0;j<rdag[i].size();j++){
      (dp[i][0]*=dp[rdag[i][j]][0])%=mod;
      (dp[i][1]*=dp[rdag[i][j]][0]+dp[rdag[i][j]][1])%=mod;
    }
    if(dag[i].size()==0)(ans*=dp[i][0]+dp[i][1])%=mod;
  }
  cout<<ans%mod<<endl;
}



Measured memory_bytes: 8160
fun main() {
    val mod = 2019
    val s = readLine()!!.reversed()
    val n = s.length

    val a = IntArray(n)
    var x = 1
    for (i in 0 until n) {
        a[i] = (s[i] - '0') * x % mod
        x = x * 10 % mod
    }

    val cs = IntArray(n + 1)
    for (i in 0 until n) {
        cs[i + 1] = (cs[i] + a[i]) % mod
    }

    var ans = 0L
    val cnt = IntArray(2019)
    for (i in 0..n) {
        ans += cnt[cs[i]]++
    }
    println(ans)
}

Measured memory_bytes: 42040
I = list(map(int,input().split()))
N = I[0]
K = I[1]
Q = I[2]
A = [0] * Q
for i in range(Q):
    A[i] = int(input())
count = [0] * N
for i in range(Q):
    count[A[i]-1] += 1
for i in range(N):
    ans = K - Q + count[i]
    if ans > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 8632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector <ll> A(N+1), B(N);
    loop(i,0,N+1) cin >> A[i];
    loop(i,0,N) cin >> B[i];
    ll sum=0;
    loop(i,0,N)
    {
        ll temp=min(A[i], B[i]);
        A[i]-=temp;
        B[i]-=temp;
        sum+=temp;
        temp=min(A[i+1], B[i]);
        A[i+1]-=temp;
        B[i]-=temp;
        sum+=temp;
    }
    cout << sum << "\n";
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using i64=int_fast64_t;
using pii=pair<int,int>;
template <class T> constexpr T inf=numeric_limits<T>::max() / (T)2;
template <class T> using minheap=priority_queue<T,vector<T>,greater<T>>;
#define fir first
#define sec second
#define mkp make_pair
#define mkt make_tuple
#define emb emplace_back
#define all(v) begin(v),end(v)




struct edge {
    int to;
    int cap;
    int rev;
    edge(int a,int b,int c) : to(a),cap(b),rev(c) {}
};

bool vis[668];
vector<edge> grh[668];

void addedge(int s,int t,int cp) {
    int ss=grh[s].size();
    int tt=grh[t].size();
    grh[s].emb(t,cp,tt);
    grh[t].emb(s,0,ss);
}

bool dfs(int x,int t) {
    vis[x]=true;
    if(x==t) return true; 
    int i=-1;
    for(auto &e:grh[x]) {
        ++i;
        if(vis[e.to] || e.cap<=0) continue;
        if(dfs(e.to,t)) {
            e.cap--;
            grh[e.to][e.rev].cap++;
            return true;
        }
    }
    return false;
}

int maxflow(int s,int t) {
    int ret=0;
    while(memset(vis,0,sizeof(vis)), dfs(s,t)) {
        ret++;
    }
    return ret;
}

int H,W,C,M,nw,nc,nm;

void solve() {
    memset(grh,0,sizeof(grh));

    const int s=300;
    const int t=301;
    const int wnone1=302,wnone2=303,cnone1=304,cnone2=305,mnone=306;

    addedge(wnone1,wnone2,nw);
    addedge(cnone1,cnone2,nc);
    addedge(mnone,t,nm);

    for(int i=0; i<H; ++i) {
        addedge(s,i,1);
        addedge(i,wnone1,1);
    }

    for(int i=0,k; i<W; ++i) {
        cin>>k;
        for(int j=0,h; j<k; ++j) {
            cin>>h;
            h--;
            addedge(h,i+H,1);
        }
        addedge(i+H,i+H+334,1);
        addedge(i+H+334,cnone1,1);
    }

    for(int i=0,k; i<C; ++i) {
        cin>>k;
        for(int j=0,w; j<k; ++j) {
            cin>>w;
            w--;
            addedge(w+H+334,i+H+W,1);
        }
        addedge(wnone2,H+W+i,1);
        addedge(i+W+H,i+H+W+334,1);
        addedge(H+W+i+334,mnone,1);
    }

    for(int i=0,k; i<M; ++i) {
        cin>>k;
        for(int j=0,c; j<k; ++j) {
            cin>>c;
            c--;
            addedge(c+H+W+334,i+H+W+C,1);
        }
        addedge(cnone2,i+H+W+C,1);
        addedge(i+H+W+C,i+H+W+C+334,1);
        addedge(i+H+W+C+334,t,1);
    }
    
    cout<<maxflow(s,t)<<endl;
}


signed main() {
    #ifdef LOCAL
        freopen("stdin.txt","rt",stdin);
    #endif

    while(cin>>H>>W>>C>>M>>nw>>nc>>nm) {
        if(max({H,W,C,M,nw,nc,nm})<0) break;
        solve();
    }
}


Measured memory_bytes: 5104
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int dp[3050][6050];
int dp2[3050][6050];

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; ++i){
    cin >> a[i] >> b[i];
  }
 
  
  for(int i = 0; i < n; ++i){
    for(int j = 0; j <= k; ++j){
      dp[i+1][j+a[i]] = max(dp[i+1][j+a[i]], dp[i][j]+b[i]);
      dp2[i+1][j+a[n-1-i]] = max(dp2[i+1][j+a[n-1-i]], dp2[i][j]+ b[n-1-i]);
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      dp2[i+1][j] = max(dp2[i+1][j], dp2[i][j]);
    }
  }
  int ans = 0;
  for(int i = 0; i < n; ++i){
    vector<int> sum(5050);
    for(int j = 0; j <= k; ++j){
      sum[j+ 1] = max(sum[j], dp2[n-1-i][j]);
    }
    
    for(int j = 0; j < k; ++j){
      ans = max(ans, dp[i][j]+sum[k-j]+b[i]);
    }
    ans = max(ans, dp[i+1][k]);
    ans = max(ans, sum[k]);
    //cout << ans << endl;
  }
  cout << ans << endl;
  
  for(int i = 0; i <= n; ++i){
    for(int j = 0; j <= k; ++j){
      //cout << dp[i][j]<< ' ';
    }
    //cout << endl;
  }
  
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int p;
    cin >> p;
    auto mod = [&](int x) {
        return (x % p + p) % p;
    };
    // Let g(x) = (x - x^p)/(x-1)
    // Clearly g(x) = 0 for all x != 1.
    // We can also write g as:
    // g(x) = - x - x^2 - ... - x^{p-1}
    // Hence g(1) = -(p-1) = 1
    // So we have g(x) = [x=1] in iversion notation.
    // So now the algorithm is simple:
    // Let I be the set of indices i for which a_i = 1.
    // The answer is then p(x) = \sum_{i \in I} g(x/i).
    // There is one small issue: What about i=0?
    // Here we can simply choose 1 - x^(p-1) instead of g(x/0).
    // Below we avoid the special case by instead of adding g(x/i) we would add:
    // 1 - (i^(p-1) - i^(p-2) x - i^(p-3) x^2 - .... - i x^(p-2) - x^(p-1))
    // Which is equal to g(x/i) for i != 0 and 1 - x^(p-1) for i = 0.
    vector<int> cs(p, 0);
    for (int i = 0; i < p; ++i) {
        int a;
        cin >> a;
        int multiplier = 1;
        for (int j = p-1; j >= 0; --j) {
            cs[j] = mod(cs[j] - multiplier * a);
            multiplier = (multiplier * i) % p;
        }
        cs[0] = mod(cs[0] + a);
    }
    for (int c : cs) {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        //g[i][j]:i番目の人がj番目の人の事を何と言っているのか(正直者=1,不親切=0,情報なし=-1)
        int[][] g = new int[N][N];
        int ans = 0;

        //全て情報なしに初期化
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                g[i][j] = -1; 
            }
        }
        //入力
        for(int i = 0; i < N; i++){
            int A = sc.nextInt();
            for(int j = 0; j < A; j++){
                int x = sc.nextInt();
                int y = sc.nextInt();
                g[i][x-1] = y; //0番目から14番目と番号を振る
            }
        }

        //2^N通りをbit全探索, iのbit列で正直者と不親切な人を決定する
        //例：0010:4人中2番目の人だけが正直者
        for(int i = 0; i < (1<<N); i++){
            int[] d = new int[N];
            for(int j = 0; j < N; j++){
                if((1 & i>>j) == 1){ //iのjbit目は1か?(右から0bit目,1bit目, ...)
                    d[j] = 1; //個々のiの場合において,j番目の人が正直者:d[j] = 1
                }
            }

            //証言が矛盾していないかをO(N^2)で調べる
            boolean ok = true;
            for(int j = 0; j < N; j++){
                if(d[j] == 1){ //正直者の言うことだけ調べる
                    for(int k = 0; k < N; k++){
                        if(g[j][k] == -1) continue; //情報なしはスキップ
                        if(g[j][k] != d[k]) ok = false;
                        //正直者のk番目の人についての証言とその真偽が一致しなかったのでこのiは矛盾
                    }
                }
            }

            //bit列iに1がいくつあるか数える(正直者の人数)
            int popcount = 0;
            for(int l = 0; l < N; l++){
                if((1 & i>>l) == 1) popcount++;
            }
            if(ok) ans = Math.max(ans, popcount);
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 25392
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int inf=2147483647;
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,m,st,ed;
struct P{int x,y;LL v;}p[85];
struct Q{int o,a,b;}q[325];
char op[3];
struct Edge{int x,y,d,next;LL c;}e[100010];
int last[450],len;
void ins(int x,int y,int d,LL c)
{
	int t=++len;
	e[t].x=x;e[t].y=y;e[t].d=d;e[t].c=c;
	e[t].next=last[x];last[x]=t;
}
void addedge(int x,int y,int d,LL c){ins(x,y,d,c),ins(y,x,0,-c);}
LL f[450];int pre[450];bool in[450];
bool spfa()
{
	memset(f,-63,sizeof(f));f[st]=0;
	memset(in,false,sizeof(in));
	queue<int>q;q.push(st);
	while(!q.empty())
	{
		int x=q.front();q.pop();in[x]=false;
		for(int i=last[x];i;i=e[i].next)
		{
			int y=e[i].y;
			if(e[i].d>0&&f[x]+e[i].c>f[y])
			{
				pre[y]=i;
				f[y]=f[x]+e[i].c;
				if(!in[y])in[y]=true,q.push(y);
			}
		}
	}
	if(f[ed]>0)return true;
	return false;
}
LL Ans,ans=0;
void work()
{
	int x=ed;
	while(x!=st)
	{
		Ans+=e[pre[x]].c;
		e[pre[x]].d--,e[pre[x]^1].d++;
		x=e[pre[x]].x;
	}
}
int lx[85],rx[85],ly[85],ry[85];
void solve(int k)
{
	memset(last,0,sizeof(last));len=1;
	for(int i=1;i<=n;i++)
	addedge(p[i].x,200+i,1,p[i].v),addedge(200+i,100+p[i].y,1,0);
	for(int i=1;i<=k;i++)lx[i]=ly[i]=1,rx[i]=ry[i]=100;
	for(int i=1;i<=m;i++)
	{
		if(q[i].o==0)lx[q[i].b+1]=max(lx[q[i].b+1],q[i].a+1);
		if(q[i].o==1&&k>q[i].b)rx[k-q[i].b]=min(rx[k-q[i].b],q[i].a-1);
		if(q[i].o==2)ly[q[i].b+1]=max(ly[q[i].b+1],q[i].a+1);
		if(q[i].o==3&&k>q[i].b)ry[k-q[i].b]=min(ry[k-q[i].b],q[i].a-1);
	}
	for(int i=2;i<=k;i++)lx[i]=max(lx[i],lx[i-1]),ly[i]=max(ly[i],ly[i-1]);
	for(int i=k-1;i;i--)rx[i]=min(rx[i],rx[i+1]),ry[i]=min(ry[i],ry[i+1]);
	st=200+n+2*k+1,ed=st+1;
	for(int i=1;i<=k;i++)
	{
		if(lx[i]>rx[i]||ly[i]>ry[i])return;
		addedge(st,200+n+i,1,0),addedge(200+n+k+i,ed,1,0);
		for(int j=lx[i];j<=rx[i];j++)addedge(200+n+i,j,1,0);
		for(int j=ly[i];j<=ry[i];j++)addedge(100+j,200+n+k+i,1,0);
	}
	int u=0;Ans=0;
	while(spfa())u++,work();
	if(u!=k)return;
	ans=max(ans,Ans);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)p[i].x=read(),p[i].y=read(),p[i].v=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		scanf("%s",op);
		q[i].a=read(),q[i].b=read();
		if(op[0]=='L')q[i].o=0;
		if(op[0]=='R')q[i].o=1;
		if(op[0]=='D')q[i].o=2;
		if(op[0]=='U')q[i].o=3;
	}
	for(int i=1;i<=n;i++)solve(i);
	printf("%lld",ans);
}


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

using namespace std;

int main(void) {
  int N, K; cin >> N >> K;
  int h[N];
  int dp[N];
  for (int i = 0; i < N; i++) {
    cin >> h[i];
    dp[i] = 0x7FFFFFFF;
  }

  dp[0] = 0;

  for (int i = 1; i < N; i++) {
    for (int j = 1; j <= K; j++) {
      if (i-j < 0) break;
      dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
    }
  }

  cout << dp[N-1] << endl;

  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
using ll = long long;
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REP2(i,s,n) for(ll i=s;i<ll(n);i++)
#define REPR(i,n) for(ll i=ll(n)-1;i>=0;i--)

int N,K;
ll ans=0;
vector<ll> V(500),T(500),S1(501),S2(501);

void print_vec(vector<ll> V,ll size){
    REP(i,size) cout<<V[i]<<" ";
    cout<<endl;
}

bool check(ll mid){
    REP(i,N) T[i]=V[i]%mid;
    sort(T.begin(),T.begin()+N);
    S1[0]=0;S2[N]=0;
    REP(i,N) S1[i+1]=S1[i]+T[i];
    REP(i,N) S2[i+1]=S2[i]+mid-T[N-i-1];
    REP2(i,1,N+1){
        ll j=N-i;
        if(S1[i]-S2[j]==0 && S1[i]<=K){
            return true;
        }
    }
    return false;
}

int main(){
    cin >> N >> K;
    REP(i,N) cin>> V[i];
    ll sum= accumulate(V.begin(),V.begin()+N,ll(0));
    ll i=1;

    for(ll i=1;i*i<=sum;i++)
    {
        if(sum%i==0){
            if(check(i) && i>=ans) ans=i;
            if(check(sum/i) && sum/i>=ans) ans=sum/i;
        }
    }

    cout<<ans<<endl;

    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP0(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define RREP0(i,n) for(int i=n-1; i>=0; --i)
#define RREP1(i,n) for(int i=n; i>=1; --i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define FILL(c, v) fill((c).begin(),(c).end(), v)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define CLR(a) memset((a), 0 ,sizeof(a))

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long LL;
typedef unsigned long long ULL;

const int INTINF = 1e9;
const LL LLINF = 1e18;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

void solve()
{
    int N; LL D, A; cin >> N >> D >> A;
    vector<pair<int, int>> X(N);

    REP0(i, N) cin >> X[i].first >> X[i].second;
    
    sort(X.begin(), X.end());

    // ある地点における爆風の総和
    LL total = 0;
    LL ans = 0;
    
    // 爆風の右端とその値
    queue<pair<LL,LL>> Q;

    REP0(i, N)
    {
        LL x = X[i].first;
        LL h = X[i].second;
        while (Q.size() and Q.front().first < x)
        { // 有効期限が切れた爆風を外しておく
            total -= Q.front().second;
            Q.pop();
        }

        h -= total;
        
        if (h > 0)
        {
            LL n_atk = (h + A - 1) / A;
            ans += n_atk;
            LL damage = n_atk * A;
            total += damage;
            Q.emplace(x + 2 * D, damage);
        }
    }
    

    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(10);
    solve();
    return 0;
}


Measured memory_bytes: 3456
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n,old,list[7];

int main(){
	while(scanf("%d",&n)*n){
		for(;n>0;n--){
			scanf("%d",&old);
			if(old<10)list[0]++;
			else if(old<20)list[1]++;
			else if(old<30)list[2]++;
			else if(old<40)list[3]++;
			else if(old<50)list[4]++;
			else if(old<60)list[5]++;
			else list[6]++;
		}
		for(n=0;n<7;n++){
			printf("%d\n",list[n]);
			list[n]=0;
		}
	}
	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll hash[1000010] = { 0 };
int main()
{
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	ll sum = 0;
	int ans;
	for (int i = 1; i <= n; i++)
	{
		ans = 0;
		if (i % 3 != 0 && i % 5 != 0)
			ans = 1;
		if (ans == 1)
			sum += i;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cmath>
using namespace std;
/* 10000a + 5000b + 1000c = Y, a+b+c=N となる a,b,cを一つ見つける
 * a=N として total < Y ならNG
 * c=N として total > Y ならNG
 * N=4でY=5000みたいなNGパターンもある
 * 10a + 5b + c = Y/1000 → 9a + 4b + N = Y/1000 となる0以上の整数a,b
 ** 9a + 4b = Y/1000 - N = sub > 0
 ** a = floor(sub/9) として，9a + 4b < sub なら b++，> sub なら a--
 */
int main(){
  int a, b, c; //temporary
  int n; // 枚数
  int y; // 金額
  int sub, sub2;
  // 入力
  cin >> n >> y;
  // 探索
  sub = y/1000 - n;
  a = floor(sub/9);
  b = 0;
  while(a>=0 && (a+b<=n)){
    sub2 = 9*a + 4*b - sub;
    if( sub2 < 0 ){ // 足りない
      b++;
    } else if( sub2 > 0 ){ // 多い
      a--;
    } else {
      break;
    }
  }
  if(a>=0 && (a+b<=n)){
    c = n - a - b;
  } else {
    a = -1;
    b = -1;
    c = -1;
  }
  cout << a << " " << b << " " << c <<endl;

  return 0;
}


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

int main() 
{
    int H, W;           //Hight, Width

    while( cin >> H >> W )
    {
        if( H == 0 && W == 0 )
            break;
        for( int i = 0; i < H; i++ )
        {
            for( int j = 0; j < W; j++ )
            {
                if( i == 0 || j == 0 || i == H - 1 || j == W - 1 )
                    cout << '#';
                else
                    cout << '.';
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3060
#include<set>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e6+10;
int a[maxn],b[maxn],c[maxn],deg[maxn],to[maxn],beg[maxn],nex[maxn],ans[maxn];
int e;
set<int> st1,st2;
priority_queue<int> q;
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
inline void add(int x,int y){
	to[++e]=y;
	nex[e]=beg[x];
	beg[x]=e;
}
int main(){
	int i,j,k,m,n;
	n=read();k=read();
	for(i=1;i<=n;i++){
		a[i]=read();
		b[a[i]]=i;
	}
	for(i=1;i<k;i++)st1.insert(a[i]);
	for(i=1;i<=n;i++){
		if(i+k-1<=n)st1.insert(a[i+k-1]);
		st1.erase(a[i-1]);
		st2.insert(a[i]);
		if(i>k)st2.erase(a[i-k]);
		set<int>::iterator cur=st1.upper_bound(a[i]);
		if(cur!=st1.end()){
			add(b[*cur],i);
			deg[i]++;
		}
		cur=st2.upper_bound(a[i]);
		if(cur!=st2.end()){
			add(b[*cur],i);
			deg[i]++;
		}
	}
	for(i=1;i<=n;i++)
		if(!deg[i])q.push(i);
	int cnt=0;
	while(!q.empty()){
		int x=q.top();
		q.pop();
		ans[++cnt]=x;
		for(i=beg[x];i;i=nex[i]){
			deg[to[i]]--;
			if(deg[to[i]]==0)q.push(to[i]);
		}
	}
	for(i=1;i<=n;i++)c[ans[i]]=n-i+1;
	for(i=1;i<=n;i++)printf("%d\n",c[i]);
	return 0;
}

Measured memory_bytes: 61824
N, Y = map(int, input().split())
x = -1
y = -1
z = -1
for i in range(N+1):
    for j in range(N-i+1):
        k = N-i-j
        if 10000*i + 5000*j + 1000*k == Y:
            x = i
            y = j
            z = k
            break
print(x,y,z)

Measured memory_bytes: 9100
#include<bits/stdc++.h>
using namespace std;
int A[26];
int main()
{
    long long i,j,k,n,m,p,q,r,t,x,y,z,zz;
    string s;
    cin>>n;
    cin>>s;
    for(i=0;i<s.size();i++)
    {
        fill(A,A+26,0);
        A[s[i]-'A']++;
        for(j=0;j<26;j++)
        {
            if(A[j]==1)
            {
                x=j;
                break;
            }
        }
        y=n;
        while(y--)
        {
            //y--;
            if(x==25)
            {
                x=0;
            }
            else
            {
               x++;
            }

        }
        cout<<char(x+'A');
    }


}


Measured memory_bytes: 256