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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

class UnionFind {
    int root(int x) {
        return parent.at(x) < 0 ? x : parent.at(x) = root(parent.at(x));
    }
    std::vector<int> parent;
    std::vector<int> sz;

public:
    UnionFind(int max) : parent(max + 1, -1), sz(max + 1, 1) {}
    void unite(int x, int y);
    int size(int x) { return sz.at(root(x)); }
    bool isFamily(int x, int y) { return root(x) == root(y); }
};

void UnionFind::unite(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
        if (parent.at(x) > parent.at(y)) std::swap(x, y);
        if (parent.at(x) == parent.at(y)) parent.at(x)--;
        sz[x] += sz[y];
        parent.at(y) = x;
    }
}

// -------------------------------------------------------------------
// sort 1 2 3 4

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

    int n, m;

    cin >> n >> m;
    vec a(m), b(m);
    init(a, b);

    vec ans;
    UnionFind uf(2e5);
    int fuben = n * (n - 1) / 2;
    ans.pb(fuben);
    Forr(i, m - 1, 1) {
        int k = a[i], l = b[i];
        if (not uf.isFamily(k, l)) {
            fuben -= uf.size(k) * uf.size(l);
            uf.unite(k, l);
        }
        ans.pb(fuben);
    }
    reverse(all(ans));
    repall (i, ans)
        print(i);

    return 0;
}

Measured memory_bytes: 6900
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int A = scan.nextInt();
		int B = scan.nextInt();
		scan.close();

		System.out.println(Math.min(N * A, B));

	}

}

Measured memory_bytes: 21844
#include<stdio.h>
#include<algorithm>
using namespace std;
char ret[70];
long long C[62][62];
int main(){
	int a;
	long long b;
	C[0][0]=1;
	for(int i=0;i<61;i++){
		for(int j=0;j<=i;j++){
			C[i+1][j]+=C[i][j];
			C[i+1][j+1]+=C[i][j];
		}
	}
	while(scanf("%d%lld",&a,&b),a){
		b=(1LL<<a)-b;
		for(int i=0;i<70;i++)ret[i]=0;
		for(int i=a;i>=0;i--){
			if(b<C[a][i]){
				int now=i;
				for(int j=0;j<a;j++){
					if(now&&b<C[a-j-1][now-1]){
						ret[j]='1';
						now--;
					}else {
						b-=C[a-j-1][now-1];
						ret[j]='0';
					}
				}
				break;
			}else b-=C[a][i];
		}
		printf("%s\n",ret);
	}
}

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

int main() {
    int cnt[2][26];

    for (int i = 0; i < 2; ++i) {
        fill(cnt[i], cnt[i] + 26, 0);
        string S;
        cin >> S;
        for (char c : S) {
            ++cnt[i][c - 'a'];
        }
        sort(cnt[i], cnt[i] + 26);
    }

    for (int j = 0; j < 26; ++j) {
        if (cnt[0][j] != cnt[1][j]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 720
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};
use std::collections::HashSet;

fn main() {
    input!{
        n: usize,
        m: usize,
        es: [(usize1, usize1); m]
    }
    if m % 2 == 1 {
        println!("-1");
        return;
    }
    let mut g = vec![HashSet::new(); n];
    for &(a, b) in &es {
        g[a].insert(b);
        g[b].insert(a);
    }
    let mut pre = vec![n; n];
    pre[0] = 0;
    dfs(0, 0, 1, &mut g, &mut pre);
    for u in 0..n {
        for &v in &g[u] {
            println!("{} {}", u + 1, v + 1);
        }
    }
}

fn dfs(r: usize, p: usize, mut next: usize, g: &mut Vec<HashSet<usize>>, pre: &mut Vec<usize>) {
    let n = g.len();
    for &c in g[r].clone().iter() {
        if c == p {
            continue;
        }
        if pre[c] < n && pre[r] < pre[c] {
            continue;
        }
        if pre[c] == n {
            pre[c] = next;
            next += 1;
            dfs(c, r, next, g, pre);
            if g[c].len() % 2 == 1 {
                g[c].remove(&r);
            } else {
                g[r].remove(&c);
            }
        } else {
            g[c].remove(&r);
        }
    }
}


Measured memory_bytes: 128508
n,K,L = gets.chomp.split(" ").map(&:to_i)
pq = K.times.map{gets.chomp.split(" ").map{|i|i.to_i-1}}
rs = L.times.map{gets.chomp.split(" ").map{|i|i.to_i-1}}
rr = Hash.new{|h,k|h[k] = Hash.new(0)}
ans = Array.new(n)    
def unifinModoki(edge,s)
  addr = Array.new(s){|i|i}
  mori = Hash.new{|h,k|h[k] = [k]}
  edge.each do |p,q|
    if addr[p] != addr[q]
      if mori[addr[p]].size < mori[addr[q]].size
        j,k = p,q
      else
        j,k = q,p
      end
      mori[addr[j]].each do |l|
        addr[l] = addr[k]
        mori[addr[k]] << l
      end
    end
  end
  return addr
end
road = unifinModoki(pq,n)
rail = unifinModoki(rs,n)
for i in 0..n-1
  rr[road[i]][rail[i]] += 1
end
for i in 0..n-1
  ans[i] = rr[road[i]][rail[i]]
end
puts ans.join("\s")

Measured memory_bytes: 83836
while True:
    h,w=map(int,input().split())
    node1=""
    node2=""
    if h==0 and w==0:
        break
    for i in range(w):
        if i%2==0:
            node1=node1+"#"
            node2=node2+"."
        elif i%2==1:
            node1=node1+"."
            node2=node2+"#"
    for i in range(h):
        if i%2==0:
            print(node1)
        elif i%2==1:
            print(node2)
    print()


Measured memory_bytes: 5612
import sys
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]

for i in range(n, 0, -1):
    val = 0
    for j in range(i, n+1, i):
        val += b[j-1]
    if val%2 != a[i-1]:
        b[i-1] += 1

num = sum(b)
if num == 0:
    print(0)
else:
    print(num)
    for i in range(n):
        if b[i] != 0:
            print(i+1)
            


Measured memory_bytes: 12192
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if(b & 1) ans = ans * a;
		b >>= 1; a = a * a;
	}
	return ans;
}
int power_mod(int a, int b, int mod) {
	a %= mod;
	int ans = 1;
	while (b) {
		if(b & 1) ans = (ans * a) % mod;
		b >>= 1, a = (a * a) % mod;
	}
	return ans;
}
LL powerl(LL a, LL b) {
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = ans * a;
		b >>= 1ll;a = a * a;
	}
	return ans;
}
LL power_modl(LL a, LL b, LL mod) {
	a %= mod;
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = (ans * a) % mod;
		b >>= 1ll, a = (a * a) % mod;
	}
	return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
const int MAXN = 100000 + 5;
int n, col[MAXN];
vector<int > G[MAXN], val[MAXN];
void dfs(int u, int fa, LL dis) {
	if (dis % 2 == 1) col[u] = 1;
	for (int i = 0; i < (int)G[u].size(); ++i) {
		int v = G[u][i];
		if (v != fa) dfs(v, u, dis + val[u][i]);
	}
}
int main() {
	cin >> n;
	for (LL u, v, w, i = 1; i < n; ++i) {
		scanf("%lld%lld%lld", &u, &v, &w);
		G[u].push_back(v);
		G[v].push_back(u);
		val[u].push_back(w);
		val[v].push_back(w);
	}
	dfs(1, 0, 0);
	for (LL i = 1; i <= n; ++i) printf("%d\n", col[i]);
	return 0;
}

Measured memory_bytes: 15232
use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;

fn exec() {
    let mut sc = Scanner::new();
    let n: i64 = sc.ne();
    let (mut lb, mut ub) = (-1i64, 1000000000i64);
    while ub - lb > 1 {
        let mid = (ub + lb) / 2;
        let val = (mid * (mid + 1)) / 2;
        if val >= n {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    println!("{}", ub);
}

fn main() {
    const STACK: usize = 16 * 1024 * 1024;
    let _ = std::thread::Builder::new()
        .stack_size(STACK)
        .spawn(|| { exec(); })
        .unwrap()
        .join()
        .unwrap();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}


Measured memory_bytes: 8572
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>

using namespace std;

int main(){

    int R, G, B, N;
    cin >> R >> G >> B >> N;

    int ans = 0;

    for(int i = 0; i <= 3000; i++){
        int tempSum1 = R * i;
        for(int j = 0; j <= 3000; j++){
            int tempSum2 = tempSum1 + G * j;
            if((N - tempSum2) >= 0 && (N - tempSum2) % B == 0){
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 2e3 + 10;
const int Mod = 1e9 + 7;

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

int Power(int a, int k)
{
	int x = 1;
	for (; k; k >>= 1)
	{
		if (k & 1) x = 1ll * x * a % Mod;
		a = 1ll * a * a % Mod;
	}
	return x;
}

int fac[maxn * maxn], inv[maxn * maxn];

void Prepare_fac(int n)
{
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i)
		fac[i] = 1ll * fac[i - 1] * i % Mod;
	inv[n] = Power(fac[n], Mod - 2);
	for (int i = n; i; -- i)
		inv[i - 1] = 1ll * inv[i] * i % Mod;
}

int C(int n, int m)
{
	if (n < 0 || n < m || m < 0) return 0;
	return 1ll * fac[n] * inv[m] % Mod * inv[n - m] % Mod;
}

int f[maxn][maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	Prepare_fac(n * k);
	if (k == 1)
	{
		puts("1");
		return 0;
	}
	f[0][0] = 1;
	for (int i = 0; i <= n; ++ i)
	{
		if (i) f[i][i] = f[i - 1][i];
		for (int j = i + 1; j <= n; ++ j)
		{
			f[i][j] = 1ll * f[i][j - 1] * C(i + j * (k - 1) - 1, k - 2) % Mod;
			if (i) Chkadd(f[i][j], f[i - 1][j]);
		}
	}
	printf("%lld\n", 1ll * f[n][n] * fac[n] % Mod);
	return 0;
}


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

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int r = sc.nextInt();
        int g = sc.nextInt();
        int b = sc.nextInt();
        int n = sc.nextInt();
        long ans = 0;
        for (int i = 0; i <= 3000; i += r) {
            for (int j = 0; j <= 3000; j += g) {
                int k = n - (i + j);
                if (k < 0) {
                    continue;
                }
                if (k % b != 0) {
                    continue;
                }
                if (i + k + j == n) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21076
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
deque<pair<int,long>> DP[301];
long A[100000];
void Calc(){
	int N = rei();
	int M = rei();
	int K = rei();
	for(int i=0;i<N;i++){
		A[i] = rel();
	}
	long ans = 0;
	for(int i=N-1;i>=0;i--){
		for(int j=K;j>1;j--){
			while(!DP[j-1].empty()){
				if(DP[j-1].front().first > i+M){
					DP[j-1].pop_front();
				}
				else{
					break;
				}
			}
			if(!DP[j-1].empty()){
				while(!DP[j].empty() && DP[j].back().second <= DP[j-1].front().second+(K-j+1)*A[i]){
					DP[j].pop_back();
				}
				DP[j].push_back({i,DP[j-1].front().second+(K-j+1)*A[i]});
			}
		}
		{
			while(!DP[1].empty() && DP[1].back().second <= K*A[i]){
				DP[1].pop_back();
			}
			DP[1].push_back({i,K*A[i]});
		}
		if(!DP[K].empty()){
			ans = max(ans,DP[K].front().second);
		}
	}
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    while(true) {
        int Q;
        scanf("%d", &Q);
        if(Q == -1) break;
        double limit = 0.00001 * Q;
        double ans = Q/2;
        while(fabs(ans*ans*ans - Q) >= limit) {
            ans = ans - (ans*ans*ans - Q) / (3*ans*ans);
        }
        printf("%f\n", ans);
    }
    return 0;
}

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

int main(){
	int joi,ioi,i,j;
	char str[10001];
	char *p;

	while(scanf("%s",str) != EOF){
		joi = 0;
		ioi = 0;
		i = 0;
		p = str;
		while(*p){
			if(!strncmp(p,"JOI",3)){
				joi++;
			}else if(!strncmp(p,"IOI",3)){
				ioi++;
			}
			*p++;
		}

		printf("%d\n%d\n",joi,ioi);
	}

	return 0;
}

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

int main() {
    int t1 = 0,
        t2 = 0,
        t3 = 0;
    vector<int> v(3);
    
    int i = 0;
    for ( ; ; i++) {
        cin >> v.at(0) >> v.at(1) >> v.at(2);
        sort(v.begin(), v.end());
        
        if ((v.at(0) + v.at(1)) <= v.at(2)) break;
        if (v.at(0) >= (v.at(1) + v.at(2))) break;
        if ((v.at(0) + v.at(2)) <= v.at(1)) break;
        
        if ((v.at(2) * v.at(2)) == (v.at(0) * v.at(0) + v.at(1) * v.at(1))) {
            t1++;
        } else if ((v.at(2) * v.at(2)) < (v.at(0) * v.at(0) + v.at(1) * v.at(1))) {
            t2++;
        } else if ((v.at(2) * v.at(2)) > (v.at(0) * v.at(0) + v.at(1) * v.at(1))) {
            t3++;
        }
    }
    //cout << v.at(0) << v.at(1) << v.at(2);
    cout << i << ' ';
    cout << t1 << ' ';
    cout << t2 << ' ';
  	cout << t3 << endl;
}


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

int main(){
  
  int N;
  cin>>N;
  
  string S[N];
  for(int i=0;i<N;i++){
    cin>>S[i];
  }
  
  int ac=0,wa=0,tle=0,re=0;
  for(int i=0;i<N;i++){
    if(S[i]=="AC"){
      ac++;
    }
    if(S[i]=="WA"){
      wa++;
    }
    if(S[i]=="TLE"){
      tle++;
    }
    if(S[i]=="RE"){
      re++;
    }
  }
   cout<<"AC x "<<ac<<endl;
   cout<<"WA x "<<wa<<endl;
   cout<<"TLE x "<<tle<<endl;
   cout<<"RE x "<<re<<endl;
}
    

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

int main(){
    int h, w;
    cin >> h >> w;
    
    string board[2002], wall = "";
    for(int i=0;i<=w+1;i++) wall.push_back('#');
    board[0] = wall;
    for(int i=1;i<=h;i++){
        string s;
        cin >> s;
        board[i] = "#" + s + "#";
    }
    board[h+1] = wall;

    static int yoko[2002][2002], tate[2002][2002];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w+1;j++){
            if(board[i][j]=='.') yoko[i][j] = yoko[i][j-1]+1;
            else{
                for(int k=1;k<=yoko[i][j-1];k++) yoko[i][j-k] = yoko[i][j-1];
                yoko[i][j] = 0;
            }
        }
    }
    for(int j=1;j<=w;j++){
        for(int i=1;i<=h+1;i++){
            if(board[i][j]=='.') tate[i][j] = tate[i-1][j]+1;
            else{
                for(int k=1;k<=tate[i-1][j];k++) tate[i-k][j] = tate[i-1][j];
                tate[i][j] = 0;
            }
        }
    }

    int ans = 0;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            ans = max(ans, yoko[i][j]+tate[i][j]-1);
        }
    }

    cout << ans << endl;
/*
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cerr << yoko[i][j] << " ";
        }
        cerr << endl;
    }
    cerr << endl;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cerr << tate[i][j] << " ";
        }
        cerr << endl;
    }
*/
    return 0;
}

Measured memory_bytes: 39424
#include <iostream>
using namespace std;
int main(){
	int a,b,d,r;
	double f;
	cin>>a>>b;
	d=a/b;
	r=a%b;
	f=(double)a/b;
	cout<<d<<" "<<r<<" "<<fixed<<f<<endl;
	return 0;
}

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

namespace id_0584cs
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            List<int> vs = new List<int>();
            foreach (var i in Enumerable.Range(0, n))
            {
                vs.Add(int.Parse(Console.ReadLine()));
            }
            vs.Sort();
            var m = 3;
            if (n != 3) { m = 4; }


            var a = vs.Take(m).Select(x=>x.ToString()).ToArray();
            List<int> results = new List<int>();

            for(int i = 0; i < m; i++)
            {
                for(int j = i+1; j<m;j++)
                {
                    results.Add(int.Parse(a[i] + a[j]));
                    results.Add(int.Parse(a[j] + a[i]));
                }
            }


            results.Sort();
            Console.WriteLine(results[2]);
        }
    }
}



Measured memory_bytes: 9880
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
  int n, num;
  string s;
  cin >> n >> s;
  rep(i, s.size()) {
    if (int(s.at(i)) > 90 - n)
      num = int(s.at(i)) - 26 + n;
    else
      num = s.at(i) + n;
    cout << char(num);
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pll;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a;
    return 0;
}


Measured memory_bytes: 3648
import java.util.Scanner;
public class Main{
	//?????°
	static int a,b;
	//????????????
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		System.out.println(a*b + " " +((a*2)+(b*2)));
	}
	public static void main(String[] args) {
		solve();
	}
}

Measured memory_bytes: 26008
var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line',function(line) {
  lines.push(line);
});
reader.on('close',function() {
  'use strict';
  var cmp = lines[0].split(' ');
  var n = Number(cmp[0]);
  var m = Number(cmp[1]);
  var list = [];
  var standard = [];
  var evaluation = [];

  for (let i = 1; i < n+1; i++) {
    list.push( Number(lines[i]) );
  }
  for (let i = n+1; i < n+m+1; i++) {
    standard.push( Number(lines[i]) );
  }
  for (let i = 0, len = list.length; i < len; i++) {
    evaluation.push(0);
  }
  for (let i = 0, len = standard.length; i < len; i++) {
    for (let j = 0, len_ = list.length; j < len_; j++) {
      if (standard[i] >= list[j]) {
        evaluation[j]++;
        break;
      }
    }
  }
  var ans = 0;
  for (let i = 0, len = evaluation.length; i < len; i++) {
    ans = Math.max(ans, evaluation[i]);
  }
  for (let i = 0, len = evaluation.length; i < len; i++) {
    if (evaluation[i] == ans) {
      console.log(i+1);
      break;
    }
  }
});



Measured memory_bytes: 18256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
int main(){
	string s;
	int k;
	cin>>s>>k;
	long long ans=0;
	if(k==1){
		for(int i=0;i<s.size();i++){
			if(i==0){
				ans+=(s[i]-'0');
			}else{
				ans+=9;
			}
		}
		cout<<ans<<endl;
	}else if(k==2){
		for(int i=1;i<s.size();i++){
			ans+=(s[0]-'0'-1)*9;
			bool f=true;
			for(int j=1;j<i;j++){
				if(s[j]!='0'){
					f=false;
				}
			}
			if(f){
				ans+=(s[i]-'0');
			}else{
				ans+=9;
			}
		}
		for(int i=1;i<s.size();i++){
			for(int j=i+1;j<s.size();j++){
				ans+=81;
			}
		}
		cout<<ans<<endl;
	}else{
		for(int i=1;i<s.size();i++){
			bool f=true;
			for(int j=1;j<i;j++){
				if(s[j]!='0'){
					f=false;
				}
			}
			for(int j=i+1;j<s.size();j++){
				ans+=(s[0]-'0'-1)*81;
				if(f){
					bool g=true;
					for(int k=i+1;k<j;k++){
						if(s[k]!='0'){
							g=false;
						}
					}
					if(g){
						if(s[i]!='0'){
							ans+=(s[i]-'0'-1)*9;
							ans+=(s[j]-'0');
						}
					}else{
						ans+=(s[i]-'0')*9;
					}
				}else{
					ans+=81;
				}
			}
		}
		for(int i=1;i<s.size();i++){
			for(int j=i+1;j<s.size();j++){
				for(int k=j+1;k<s.size();k++){
					ans+=729;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
// Author: Moulik
// Date Created: 07 June 2020
// Filename: C.cpp
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define what_is(x) cerr << "DEBUG::BEGIN\n\tVariable name:\n\t\t" << #x << "\n\tdata:\n\t\t" << x << "\nDEBUG::END" << endl;
#else
#define what_is(x) ;
#endif

// DEFINE OSTREAMS HERE

template<typename T1, typename T2>
ostream & operator<<(ostream &os, const pair<T1,T2> p){
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<typename T>
ostream & operator<<(ostream &os, const vector<T> p){
    os << "{ ";
    for(auto i:p){
        os << i << ",";
    }
    os << "\b";
    os << "}";
    return os;
}

// DEFINE ISTREAMS HERE

template<typename T1, typename T2>
istream & operator >> (istream &in, pair<T1,T2> & p){
    in >> p.first >> p.second;
    return in;
}

// Sorts array in the given order {key is 0 indexed}
template<typename T>
void keySort(vector<T> & arr, vector<int> & key){
    int n = arr.size();
    if(key.size()!=n){
        throw runtime_error("Size of data array not equals to size of key array");
    }
    vector<T> ans(n);
    int ar[n];
    for(int i = 0; i < n; i++){
        ar[key[i]]=i;
    }
    for(int i = 0; i < n; i++){
        ans[i] = arr[ar[i]];
    }
    arr = ans;
}
void solve();

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

vector<int> vc(10,1);

bool check(int n){
    string s = to_string(n);
    for(auto i:s){
        if(vc[i-'0']==0){return false;}
    }
    return true;
}

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < k; i++){
        int _;
        cin >> _;
        vc[_]=0;
    }
    for(int i = n; i <= 10*n; i++){
        if(check(i)){
            cout << i << endl;
            return ;
        }
    }
}

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

// 強連結成分分解 O(N+M)
// verify
struct StronglyConnectedComponents {
private:
    vector<vector<int>> g, rg;
    vector<int> order; // dfsの順
    vector<bool> visited;
    int V;

    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (int u : g[v]) dfs(u);
        order.push_back(v);
    }

    void rdfs(int v, int c) {
        if (comp[v] != -1) return;
        comp[v] = c;
        for (int u : rg[v]) rdfs(u, c);
    }

public:
    vector<vector<int>> Graph; // DAG(多重辺アリ)
    vector<int> comp; // comp[i] : iが属する成分

    StronglyConnectedComponents(int v) : V(v) {
        g.resize(v);
        rg.resize(v);
        visited.resize(v);
        comp.resize(v);
    }

    void add_edge(int from, int to) {
        g[from].push_back(to);
        rg[to].push_back(from);
    }

    void build() {
        Graph = vector<vector<int>>();
        order = vector<int>();
        visited.assign(V, false);
        comp.assign(V, -1);
        for (int i = 0; i < V; i++) dfs(i);
        reverse(order.begin(), order.end());
        int number = 0;
        for (int i = 0; i < V; i++) {
            if (comp[order[i]] == -1) {
                rdfs(order[i], number++);
            }
        }
        Graph.resize(number);
        for (int i = 0; i < V; i++) {
            for (int v : g[i]) {
                if (comp[i] == comp[v]) continue;
                Graph[comp[i]].push_back(comp[v]);
            }
        }
    }
};

int main() {
    int n, m; cin >> n >> m;
    StronglyConnectedComponents G(n);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        G.add_edge(a, b);
    }
    G.build();
    int q; cin >> q;
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        if (G.comp[a] == G.comp[b]) ans[i] = 1;
        else ans[i] = 0;
    }
    //dump(G.comp);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 4520
#include<iostream>
using namespace std;
int main()
{
    
    int n,x,a;
    
    cin>>n;
    
    
    for(a=1;a<=3;a++)
    {
        
        x=n%10;
        
        if(x==7)
        {
            
            
            cout<<"Yes"; break;
            
            
        }
        
        n=n/10;
        
        
    }
    
    
    if(a==4)
    {
        
        cout<<"No";
    
    }
    
    
}


Measured memory_bytes: 3608
n = gets.strip.to_i
s = gets.strip.split('')

four_types = ['SS', 'SW', 'WS', 'WW'].map {|line| line.split('') }

def valid_trinity(arr, saying)
  return arr[0] == arr[2] if arr[1] == 'S' && saying=='o'
  return arr[0] != arr[2] if arr[1] == 'S' && saying=='x'
  return arr[0] != arr[2] if arr[1] == 'W' && saying=='o'
  return arr[0] == arr[2] if arr[1] == 'W' && saying=='x'
end

four_types.each do |candidate|
  current = candidate.dup
  (2...n).each do |i|
    pair = current[-2..-1]
    
    if pair[1]=='S' 
      current.push('S') if s[i-1]=='x' && pair[0]=='W' 
      current.push('W') if s[i-1]=='o' && pair[0]=='W' 
      current.push('W') if s[i-1]=='x' && pair[0]=='S' 
      current.push('S') if s[i-1]=='o' && pair[0]=='S' 
    else
      current.push('W') if s[i-1]=='x' && pair[0]=='W' 
      current.push('S') if s[i-1]=='o' && pair[0]=='W' 
      current.push('S') if s[i-1]=='x' && pair[0]=='S' 
      current.push('W') if s[i-1]=='o' && pair[0]=='S' 
    end

    break if current.length<=i
  end
  if current.length==n
    last2first1 = current[-2..-1] + [current.first]
    last1first2 = [current.last] + current[0..1]

#p [last2first1, s.first]

    if valid_trinity(last2first1, s.last) && valid_trinity(last1first2, s.first)
      puts current.join('')
      exit
    end
  end
end

p -1




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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int cntr = 0;
  rep(i,n){
    if(s[i] == 'R') cntr++;
  }
  int ans = 0;
  rep(i,cntr){
    if(s[i] == 'W') ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3724
s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)

Measured memory_bytes: 4320
import java.util.*;

public class Main {

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

		int n=0;
		String[] s = new String[100];

		while(sc.hasNext()){
			s[n] = sc.next();
			n++;
		}
		
		int[][] map = new int[n][n];
		int[][] cost = new int[n][n];
		
		for(int i=0;i<n;i++){
			int z;
			if(i<=n/2){
				z=i;
			}else{
				z=n-i-1;
			}
			
			int sum = 0;
			int count = 0;
			int start = 0;
			for(int j=0;j<z;j++){
				start = count;
				while(s[i].substring(count,count+1).compareTo(",")!=0)count++;
				map[i][j] = Integer.valueOf(s[i].substring(start,count));
				count++;
			}
			map[i][z] = Integer.valueOf(s[i].substring(count,s[i].length()));		
		}
		
		cost[0][0] = map[0][0];
		
		for(int j=1;j<n;j++){
			int z, flag;
			if(j<=n/2){
				z=j;
				flag=1;
			}else{
				z=n-j-1;
				flag=-1;
			}
			
			for(int k=0;k<=z;k++){
				if(k==0 && flag==1){
					cost[j][k] = cost[j-1][k]+map[j][k];
				}else if(cost[j-1][k]>cost[j-1][k-1*flag]){
					cost[j][k] = cost[j-1][k]+map[j][k];
				}else{
					cost[j][k] = cost[j-1][k-1*flag]+map[j][k];
				}
			}
		}
		
		System.out.println(cost[n-1][0]);
		
	}
}

Measured memory_bytes: 23404
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    string s;
    string ret;
    cin >> s;
    for(auto p : s){
        if(p=='0') ret.push_back('0');
        if(p=='1') ret.push_back('1');
        if(p=='B' and !ret.empty()) ret.pop_back();
    }
    cout << ret << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
}

Measured memory_bytes: 3572
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <climits>

using namespace std;
using ll  = long long;
template <typename T> T In() {
    T t;
    cin >> t;
    return t;
}
template <typename T> vector<T> ReadVec1(int N) {
    vector<T> vec(N);
    for(int i = 0; i < N; i++)
        vec[i] = In<T>();
    return move(vec);
}
template <typename T> vector<vector<T>> Vec2(int i, int j, T ini = 0) {
    vector<vector<T>> vec(i, vector<T>(j, ini));
    return move(vec);
}
template <typename T> vector<vector<vector<T>>> Vec3(int i, int j, int k, T ini = 0) {
    vector<vector<vector<T>>> vec(i, vector<vector<T>>(j, vector<T>(k, ini)));
    return move(vec);
}

int main() {
    int N = In<int>(), a, b, c;
    auto dp = Vec2<int>(N + 1, 3);
    for(int n = 1; n <= N; n++) {
        cin >> a >> b >> c;
        dp[n][0] = max(dp[n - 1][1], dp[n - 1][2]) + a;
        dp[n][1] = max(dp[n - 1][0], dp[n - 1][2]) + b;
        dp[n][2] = max(dp[n - 1][0], dp[n - 1][1]) + c;
    }
    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}

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

int N;
vector<long long> a;
long long res;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  a.resize(3 * N);
  for (int i = 0; i < 3 * N; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < N; ++i) {
    res += a[3 * N - 2 * i - 2];
  }
  cout << res << endl;
}

Measured memory_bytes: 2560
n,m=map(int,input().split())
h=list(map(int,input().split()))
ans=[1 for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]<h[b-1]:
        ans[a-1]=0
    elif h[a-1]>h[b-1]:
        ans[b-1]=0
    else:
        ans[a-1]=0
        ans[b-1]=0
print(sum(ans))

Measured memory_bytes: 20116
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct jiedian{
  int key;
  jiedian *prev;
  jiedian *next;
};
jiedian *nil;

jiedian *sousuo(int key){
  jiedian *cur = nil->next;
  while(cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void init(){
  nil=(jiedian *)malloc(sizeof(jiedian));
  nil->prev = nil;
  nil->next = nil;
}
void shuchu(){
  jiedian *cur = nil->next;
  int isf = 0;
  while(1){
    if(cur == nil)break;
    if(isf++ > 0)printf(" ");
    printf("%d",cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void shanchu(jiedian *t){
  if(t == nil)return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void shanchu1(){
  shanchu(nil->next);
}

void shanchu2(){
  shanchu(nil->prev);
}

void shanchukey(int key){
  shanchu(sousuo(key));
}
void shuru(int key){
  jiedian *x=(jiedian *)malloc(sizeof(jiedian));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key,n,i;
  char com[20];
  scanf("%d",&n);
  init();
  for(i = 0;i < n; i++){
    scanf("%s%d",com,&key);
    if(com[0] == 'i'){shuru(key);}
    else if(com[0] == 'd'){
      if(strlen(com) > 6){
        if(com[6] == 'F')shanchu1();
        else if(com[6] == 'L')shanchu2();
      }
      else{
        shanchukey(key);
      }

    }
  }
  shuchu();
  return 0;
}

Measured memory_bytes: 33864
//g++ main.cpp -I /usr/local/include/ac-library
#include<cmath>

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

stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
#define ALL(a) a.begin(), a.end()
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
typedef vector<ll> vec;
typedef vector<vec> mat;


int main(){
    int n;
    cin >> n;
    vec p(n+1),a(n+1),b(n+1);
    rep(i,n){
        cin >> p[i];
        a[i]=30000*(i+1);
        b[i]=30000*(n-i);
    }
    rep(i,n){
        b[p[i]-1]+=i;
    }
    rep(i,n){
        cout<<a[i];
        if(i!=n-1){
            cout<<' ';
        }
    }
    cout<<endl;
    rep(i,n){
        cout<<b[i];
        if(i!=n-1){
            cout<<' ';
        }
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3880
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
const int mod=1000000007;
using namespace std;
ll n,f[1000005],s;
int main(){
    cin>>n;
    f[n]=n;
    f[n-1]=n*n%mod;
    for(reg int i=n-2;i>=1;i--){
        s=(s+f[i+3])%mod;
        f[i]=(f[i+1]+(n-1)*(n-1)%mod+s+i+1)%mod;
    }
    printf("%d\n",f[1]);
    return 0;
}

Measured memory_bytes: 8064
//
//  main.cpp
//  temp
//
//  Created by 松本拓真 on 2018/02/25.
//  Copyright © 2018年 TakumaMatsumoto. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cgt(vector<size_t> &cards, int alice = 0, int bob = 0) {
    sort(cards.begin(), cards.end(), [](size_t lhs, size_t rhs) {
        return lhs > rhs;
    });
    auto mode = 0;
    for (auto c : cards) {
        if (mode == 0)
            alice += c;
        else
            bob += c;
        mode = ++mode % 2;
    }
    return alice - bob;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int n;
    cin >> n;
    vector<size_t> a;
    for (auto i = 0; i < n; i++) {
        int v; cin >> v;
        a.push_back(v);
    }
    cout << cgt(a);
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    int a; cin >> a;
    if(a<3200){cout << "red" << endl; return 0;}
    string s; cin >> s;
    cout << s << endl;
    return 0;
}



Measured memory_bytes: 256
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
for i in range(h):
    l = ''
    for j in range(w):
        if s[i][j] == '#':
            l += s[i][j]
        else:
            l += str(sum([t[max(0, j-1): min(j+2, w)].count('#')
                          for t in s[max(0, i-1): min(h, i+2)]]))
    print(l)

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()


int main(){
    int N;
    ll Co=0,Pnum,Qnum;
    cin>>N;
    vector<int>P(N),Q(N),PN(N);
    rep(i,N)cin>>P[i];
    rep(i,N){
        cin>>Q[i];
        PN[i]=i+1;
    }

    do{
        Co++;
        bool p=true,q=true;
        rep(i,N){
            if(PN[i]!=P[i])p=false;
            if(PN[i]!=Q[i])q=false;
        }
        if(p)Pnum=Co;
        if(q)Qnum=Co;
    }while(next_permutation(PN.begin(),PN.begin()+N));

    cout<<abs(Pnum-Qnum)<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

struct Ans{
  int x;
  int y;
  int z;
};
static const int E_MAX = 1000001;
static const int Y_MAX = 1000;
static const int Z_MAX = 100;
Ans ans[ E_MAX ];

int main (){
  for( int i = 0; i < E_MAX; i++ ) {
    ans[ i ].x = -1;
  }

  for( int y = 0; y <= Y_MAX; y++ ) {
    for( int z = 0; z <= Z_MAX; z++ ) {
      int idx = y * y + z * z * z;
      if( idx >= E_MAX ){ break; }
      if( ans[ idx ].x != -1 ) {
        if(
            y + z < ans[ idx ].y + ans[ idx ].z
        ) {
          ans[ idx ].y = y;
          ans[ idx ].z = z;
        }
        continue;
      }
      ans[ idx ].x = 0;
      ans[ idx ].y = y;
      ans[ idx ].z = z;
    }
  }

  int counter = 0;
  int py = -1, pz = -1;
  for( int i = 0; i < E_MAX; i++ ) {
    if( ans[ i ].x != -1 ) {
      if(
          counter + py + pz < ans[ i ].y  + ans[ i ].z &&
          py != -1 && pz != -1
       ){
        ans[ i ].x = ++counter;
        ans[ i ].y = py;
        ans[ i ].z = pz;
      }else{
        counter = 0;
        py = ans[ i ].y;
        pz = ans[ i ].z;
      }
      continue;
    }
    ans[ i ].x = ++counter;
    ans[ i ].y = py;
    ans[ i ].z = pz;
  }
  while( 1 ) {
    int e;
    cin >> e;
    if( !e ){ return EXIT_SUCCESS; }
    cout << ans[ e ].x + ans[ e ].y + ans[ e ].z << endl;
  }
}

Measured memory_bytes: 12872