akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Mod
{
private:
    static const int MOD = 1000000007;
    long long a;
public:
    Mod(){
        a = 0;
    }
    Mod(long long x){
        a = (x % MOD + MOD) % MOD;
    }
    const Mod operator+(const Mod& x) const{
        return Mod(a + x.a);
    }
    const Mod operator-(const Mod& x) const{
        return Mod(a - x.a);
    }
    const Mod operator*(const Mod& x) const{
        return Mod(a * x.a);
    }
    const Mod operator/(const Mod& x) const{ // フェルマーの小定理、MODが素数である場合のみ有効
        int b = MOD - 2;
        long long c = x.a;
        long long ret = 1;
        while(b > 0){
            if(b & 1){
                ret *= c;
                ret %= MOD;
            }
            c *= c;
            c %= MOD;
            b >>= 1;
        }
        return Mod(a * ret);
    }
    long long getValue(){
        return a;
    }
};

int main()
{
    int n, k;
    cin >> n >> k;
    if(k == 1){
        cout << 1 << endl;
        return 0;
    }

    vector<Mod> factorial(n*k+1, 1);
    for(int i=1; i<=n*k; ++i)
        factorial[i] = factorial[i-1] * i;

    vector<vector<Mod> > dp(n+1, vector<Mod>(n+1, 0));
    dp[0][0] = 1;
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=i; ++j){
            if(i < n)
                dp[i+1][j] = dp[i+1][j] + dp[i][j];
            if(j < i){
                int x = (n - i) + (k - 1) * (n - j);
                dp[i][j+1] = dp[i][j+1] + dp[i][j] * factorial[x-1] / (factorial[k-2] * factorial[x-k+1]);
            }
        }
    }

    Mod ans = dp[n][n] * factorial[n];
    cout << ans.getValue() << endl;

    return 0;
}

Measured memory_bytes: 62848
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
typedef long long ll;

int main()
{
	string s;
	cin >> s;
	s[5] = ' ';
	s[13] = ' ';
	cout << s << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
ll A[1010];
ll N;
ll MOD =1e9+7;

int main(){
	cin>>N;
  	for (int i=2;i<=N;++i){
      	ll t = i;
    	for (int j=2;j<=i;++j){
          	ll c = 0;
        	while (t%j == 0){
            	++c;
              	t /= j;
            }
          	A[j] += c;
        }
    }
  	ans = 1;
  	for (int i=1;i<=N;++i)ans = (ans * (A[i]+1) % MOD);
  	cout<<ans;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()		// begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)				// repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)			// repeat reverse

#endif

class ABC133D
{
public:
	ABC133D()
	{
		cin >> n;

		a.resize(n);
		rep(i, 0, n)
			cin >> a[i];
	}
	void Run(void)
	{
		vector<ll> ans(n);
		
		repr(i, n - 1, -1)
			ans[0] += (i % 2 == 0) ? a[i] * 2: -a[i] * 2;
		ans[0] /= 2;

		rep(i, 1, n)
			ans[i] = a[i - 1] * 2 - ans[i - 1];

		for (const auto& e : ans)
			cout << e << " ";
	}
private:
	ll n;
	vector<ll> a;
};

int main(void)
{
	ABC133D abc133d;
	abc133d.Run();

	return 0;
}


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

using namespace std;

#define endl '\n'

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

ll gcd(ll a, ll b, ll &x, ll &y)
{
	if(b == 0)
		return x = 1, y = 0, a;
	ll r = gcd(b, a % b, y, x);
	y -= a / b * x;
	return r;
}

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

	ll a, b;
	cin >> a >> b;

	ll x, y;
	gcd(a, b, x, y);

	cout << x << " " << y << endl;

	return 0;
}

Measured memory_bytes: 1192
def count(b, e, k, ary):
    sum = 0
    for elem in ary[b:e]:
        if elem == k:
            sum += 1
    return sum


def main():
    n = int(input())
    ary = [int(x) for x in input().split(" ")]
    num_q = int(input())
    for i in range(num_q):
        b, e, k = [int(x) for x in input().split(" ")]
        print(count(b, e, k, ary))


if __name__ == '__main__':
    main()



Measured memory_bytes: 5716
//ProblemD

#ifdef _MYPC
#include "mypc.h"
#endif // _MYPC

#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <memory>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

//ProblemD

#define MAXN 200010

class Solve {
private:
	int n;
	long long a[MAXN], b[MAXN], c[MAXN];
	void solve() {
		cin >> n;
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < n; i++) cin >> b[i];

		long long rst = 0;
		for (long long msk = 1; msk <= (1 << 28); msk <<= 1) {
			long long mod = msk << 1;

			for (int i = 0; i < n; i++) c[i] = b[i] % mod;
			sort(c, c + n);

			long long cnt = 0;
			for (int i = 0; i < n; i++) {
				auto ma = a[i] % mod;
				auto minb = (mod - ma) % mod;
				auto maxb = (mod - ma + mod / 2) % mod;

				auto left = lower_bound(c, c + n, minb);
				auto right = lower_bound(c, c + n, maxb);

				
				if (maxb > minb) {
					cnt += n - (right - left);
				}
				else {
					cnt += left - right;
				}
			}

			if (cnt % 2 == 1) rst |= msk;
		}
		cout << rst << endl;
	}

public:
	Solve() { solve(); }
};

int main(int argc, char* argv[]) {
	unique_ptr<Solve> solve = make_unique<Solve>();
	return 0;
}


Measured memory_bytes: 4992
import sys
input=sys.stdin.readline
import math

def main():
    N,K = map(int, input().split())
    A = {}
    for _ in range(N):
        a,b = map(int, input().split())
        if a in A:
            A[a] += b
        else:
            A[a] = b
    A = sorted(A.items(), key=lambda x:x[0])
#    print(A)
    for a,b in A:
        K -= b
        if K <= 0:
            print(a)
            break

if __name__ == '__main__':
    main()


Measured memory_bytes: 15068
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N int
	_, _ = fmt.Scan(&N)
	a := make([]int, N)
	for i := 0; i < N; i++ {
		_, _ = fmt.Scan(&a[i])
	}
	sort.Sort(sort.IntSlice(a))
	var w float64
	w = float64(a[0]+a[1]) / 2
	for i := 2; i < N; i++ {
		w = (w + float64(a[i])) / 2
	}
	fmt.Println(w)

}


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

int main(int argc, char** argv){
	int n;
	cin >> n;
	vector<vector<int> > a(n);
	int idx[n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n-1; j++){
			int t;
			cin >> t;
			a[i].push_back(t-1);
		}
		idx[i] = 0;
	}
	int day = 0;
	bool flag[n];
	bool f;
	bool finish;
	vector<int> next(n);
	while(true){
		f = true;
		finish = true;
		for(int i = 0; i < n; i++){
			next[i] = (idx[i] < n-1) ? a[i][idx[i]] : -1;
			flag[i] = true;
			if(idx[i] < n-1){
				finish = false;
			}
		}
		if(finish){
			break;
		}
		for(int i = 0; i < n-1; i++){
			if((i == next[next[i]]) && flag[i]){
				idx[i]++;
				idx[next[i]]++;
				flag[i] = false;
				flag[next[i]] = false;
				f = false;
			}
		}
		if(f){
			day = -1;
			break;
		}
		day++;
	}
	cout << day << endl;
	return 0;
}


Measured memory_bytes: 6272
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long

using namespace std;
using namespace __gnu_pbds;

template <class T> using ordered_set =
tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;

const int N = (int)(1e6 + 5);
const int M = (int)(1e9 + 7);
const int INF = (int)(1e18 + 9);
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};

signed main() {
  ios_base :: sync_with_stdio(0);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  if (a <= 0 && b >= 0) {
    cout << "Zero";
  }
  else if (a < 0 && b < 0) {
    cout << ((abs(a) - abs(b) + 1) % 2 == 0 ? "Positive" : "Negative");
  }
  else {
    cout << "Positive";
  }
  return 0;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n;
	double d, x, ans = 0; cin >> n >> d >> x;
	for(; n > 1; n--){
		double d0 = (6 * d + 5 * x) / (2 * n) + d * (n - 2) / n;
		double d1 = (6 * d + 13 * x) / (2 * n) + (d + x) * (n - 2) / n;
		
		ans += d + x * (2 * n - 1) / 2;
		x = d1 - d0;
		d = d0;
	}
	ans += (2 * d + x) / 2;
	printf("%.20f\n", ans);
	
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
const int MAX = 100000;

int A[MAX],n;

int partition(int p,int r){
int x,i,j,t;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
    if(A[j]<=x){
        i++;
        t = A[i];A[i]=A[j];A[j] = t;
    }
}
t = A[i+1];A[i+1] = A[r];A[r] = t;
return i+1;
}

int main(){
int i,q;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&A[i]);
q = partition(0,n-1);
for(i=0;i<n;i++){
    if(i)printf(" ");
    if(i==q)printf("[");
    printf("%d",A[i]);
    if(i==q)printf("]");
}
printf("\n");
return 0;
}



Measured memory_bytes: 2976
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int keta = (int)Math.Log10(n) + 1;
            //Console.WriteLine(keta);

            switch (keta)
            {
                case (1):
                    Console.WriteLine(n);
                    break;
                case (2):
                    Console.WriteLine(9);
                    break;
                case (3):
                    int n3 = n - 100 + 1;
                    Console.WriteLine(9 + n3);
                    break;
                case (4):
                    Console.WriteLine(9 + 900);
                    break;
                case (5):
                    int n5 = n - 10000 + 1;
                    Console.WriteLine(9 + 900 + n5);
                    break;
                case (6):
                    Console.WriteLine(9 + 900 + 90000);
                    break;
                    
            }

        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long LL;
LL i,j,k,n,m;
LL mod=1000000007;
string s;

int main() {
  cin >>n;
  map<LL, LL> mp;
  for(i=0;i<n;++i) {
    LL t;cin >> t;
    if(mp.find(t) != mp.end()) {
      mp.at(t) = mp.at(t) + 1;
    } else {
      mp.insert(make_pair(t,1));
    }
  }
  int cnt=0;
  for(auto itr=mp.begin();itr !=mp.end();++itr){
    if((*itr).second%2 != 0) ++cnt;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const int N = 1e5;
ll n, k;
ll w[N], d[N];

ll count(ll x){
    ll ret = 0;
    REP(i,n){
        if (x >= w[i]) ret += 1 + (x - w[i]) / d[i];
        if (ret > k) return ret;
    }
    return ret;
}

int main() {
    cin >> n >> k;
    REP(i,n) scanf("%lld %lld", w+i, d+i);

    ll le = 0, ri = 2e18;
    while (ri - le > 1){
        ll mi = le + (ri - le) / 2;
        if (count(mi) >= k) ri = mi;
        else le = mi;
    }
    cout << ri << endl;

    return 0;
}




Measured memory_bytes: 1920
#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int a[200005];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int Ans = a[n] - a[1];
    for (int i = 2; i <= n; i++)
    {
        Ans = min(Ans, k - (a[i] - a[i - 1]));
    }
    cout << Ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const i64 mod = 1e9 + 7;
string s;
i64 n;
vector<array<i64, 13>> dp;
int main() {
  cin >> s;
  n = s.size();
  reverse(begin(s), end(s));

  init_n(dp, n + 1);
  dp[0][0] = 1;
  for (i64 i = 1, k = 1; i <= n; ++i, k = 10 * k % 13) {
    for (i64 j = 0; j < 13; ++j) {
      if (s[i - 1] == '?') {
        for (i64 x = 0; x <= 9; ++x) {
          i64 l = (j + x * k) % 13;
          dp[i][l] += dp[i - 1][j];
          dp[i][l] %= mod;
        }
      } else {
        i64 x = s[i - 1] - '0';
        i64 l = (j + x * k) % 13;
        dp[i][l] += dp[i - 1][j];
        dp[i][l] %= mod;
      }
    }
  }
  cout << dp[n][5] << endl;
  return 0;
}


Measured memory_bytes: 10624
#include "bits/stdc++.h"
using namespace std;
#define dump(x) cout << (x) << endl;
typedef int64_t Int;
Int mod = 1e9+7;

int main() {
  Int n, a;
  cin >> n >> a;
  vector<Int> x(n);
  for (Int i = 0; i < n; i++) cin >> x[i];
  Int dp[51][5001] = {};
  dp[0][2500] = 1;
  for (Int i = 0; i < n; i++) {
    for (Int j = 0; j < 5000; j++) {
      dp[i + 1][j] += dp[i][j];
      Int add = x[i] - a;
      if (0 <= add + j && add + j <= 5000) {
        dp[i + 1][j + add] += dp[i][j];
      }
    }
  }
 /*  for (Int i = 0; i <= n; i++) {
    for (Int j = 2500 - 3; j < 2500 + 3; j++) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  } */
  dump(dp[n][2500] - 1);
  return 0;
}


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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define For(i, a, b) for (ll i = (a); i < (b); i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N;
    cin >> N;
    int A[N];
    rep(i, N) cin >> A[i];
    bool flag = true;
    rep(i, N) {
        if (A[i] % 2 == 0) {
            if (A[i] % 3 != 0) if (A[i] % 5 != 0) flag = false;
            
        } 
    }
    if (flag) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;


    return 0;
}


Measured memory_bytes: 256
use std::io::{BufRead, StdinLock};
use std::str::FromStr;

fn read<T: FromStr>(stdin_lock: &mut StdinLock, buf: &mut Vec<u8>, delimiter: u8) -> T {
    buf.clear();
    let l = stdin_lock.read_until(delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let b = read(&mut stdin_lock, &mut buf, b'\n');
    println!("{}", solve(b));
}

fn solve(a: String) -> &'static str {
    match a.as_str() {
        "A" => "T",
        "C" => "G",
        "G" => "C",
        "T" => "A",
        _ => panic!("invalid")
    }
}

#[test]
fn example1() {
    assert_eq!("T", solve("A".to_owned()))
}

#[test]
fn example2() {
    assert_eq!("C", solve("G".to_owned()))
}


Measured memory_bytes: 4352
#pragma region noncode
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SORT(v) sort(all(v))
#define TROS(v) sort(all(v), std::greater<Type>());
#pragma endregion

int main() {
    // template
    int a,b,c;cin>>a>>b>>c;
    int res = 100000000;
    res = min(abs(a-b)+abs(b-c),res);
    res = min(abs(b-c)+abs(c-a),res);
    res = min(abs(c-a)+abs(a-b),res);
    cout<<res<<endl;
}


Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
static const int N = 100000;
static const int NIL = -1;
int n;
vector<int> G[N];
int reach[N];
void dfs(int r, int c) {
    stack<int> S;
    S.push(r);
    reach[r] = c;
    while (!S.empty() ) {
        int u = S.top(); S.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v =  G[u][i];
            if (reach[v] == NIL) {
                reach[v] = c;
                S.push(v);
            }
        }
    }
}
void assign() {
    int id = 1;
    for (int i = 0; i < n; i++) reach[i] = NIL;
    for (int u = 0; u < n; u++)
        if (reach[u] == NIL) dfs(u, id++);
}
int main() {
    int s, t, m, q;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    assign();
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> s >> t;
        if (reach[s] == reach[t]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}



Measured memory_bytes: 9004
solve :: [Int] -> Int -> Int
solve l n
    | all (\x -> (even x && x > 0)) l = solve (map (`div` 2) l) $ n + 1
    | otherwise = n

main = do
    _ <- getLine
    t <- (map read . words) <$> getLine
    putStrLn $ show $ solve t 0


Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define eb emplace_back
#define MP make_pair
#define pb push_back
#define pf push_front
#define ins insert
#define all(v) (v).begin(), (v).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define tr(c,it) for(auto it=c.begin();it!=c.end();it++)
#define fr(i,n) for(lli i=0;i<(n);i++)
#define inc(i,a,b) for(lli i=a;i<=b;i++)
#define dec(i,a,b) for(lli i=a;i>=b;i--)
#define fr2(i,n) for(int i=0;i<(n);i++)
#define inc2(i,a,b) for(int i=a;i<=b;i++)
#define dec2(i,a,b) for(int i=a;i>=b;i--)
#define ymin(a,b)  (a=min((a),(b)))
#define ymax(a,b)  (a=max((a),(b)))
#define sz(x) (lli)(x).size()
typedef long long int lli;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef vector<lli> vlli;
typedef vector<int> vi;
//typedef  vector<vector<lli> >ncr(1001,vector<lli>(1001,0))
typedef vector<plli> vplli;
long long MOD=1000000007;
double startTime;
double getCurrentTime()
{
	return ((double)clock()-startTime)/CLOCKS_PER_SEC;
}

lli pwr(lli x,lli n)
{
	lli res=1;
	for(; n!=0;n>>=1)
	{
		if(n&1)
			res=(res*x)%MOD;
		x=(x*x)%MOD;
	}
	return res;
}
lli inver(lli num)
{
	return pwr(num,MOD-2);
}
lli findncr(lli n,lli r)
{
	r=min(r,n-r);
	if(n==0||n==1||r==0)
		return 1;
	lli numer=1;
	for(lli i=n;i>=n-r+1;i--)
		numer=(numer*i)%MOD;
	lli den=1;
	for(lli i=2;i<=r;i++)
		den=(den*i)%MOD;
	den=inver(den);
	lli res=(numer*den)%MOD;
	return res;
}
lli gcd(lli a,lli b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
int main()
{
	// 	#ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS
	int h,w;
	cin>>h>>w;
	vector<vector<lli> >dp(h+1,vector<lli>(w+1,0));
	vector<vector<char> >grid(h+1,vector<char>(w+1,' '));
	for(int i=1;i<=h;i++)
	{
		//string str;
		//cin>>str;
		for(int j=1;j<=w;j++)
		cin>>grid[i][j];

	}
	// for(int i=1;i<=h;i++)
	// {
	// 	//string str;
	// 	//cin>>str;
	// 	for(int j=1;j<=w;j++)
	// 	//cin>>grid[i][j];
	// 		cout<<grid[i][j];
	// 	cout<<endl;

	// }
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(grid[i][j]=='#')
				continue;
			else if(i==1 && j==1)
				dp[i][j]=1;
			else
				dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
		}
	}
	cout<<dp[h][w]<<endl;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s; cin >> s;
	ll i = 0, j = sz(s)-1, res = 0;
	while (i < j) {
		res += s[i] != s[j];
		i++, j--;
	}
	cout << res << endl;
}



Measured memory_bytes: 256
import java.util.*;
public class Main {
	final int [][] spRange ={
			{-1,-1},{0,-1},{1,-1},
			{-1,0}, {0,0},{1,0},
			{-1,1},{0,1},{1,1}};
	final int [][] pyonRange = {
			{-1,-2},{0,-2},{1,-2},
			{-2,-1},{2,-1},
			{-2,0},{2,0},
			{-2,1},{2,1},
			{-1,2},{0,2},{1,2}};

	int [][] sp;

	private boolean isOutRange(int n){
		if(n < 0 || n >= 10){
			return true;
		}
		else{
			return false;
		}
	}

	private boolean isRangeSP(int x, int y, int index){
		int spx = sp[index][0];
		int spy = sp[index][1];
		for(int i=0; i < spRange.length; i++){
			int pattRangeX = spx + spRange[i][0];
			int pattRangeY = spy + spRange[i][1];
			if(isOutRange(pattRangeX) || isOutRange(pattRangeY))
				continue;
			if(x == pattRangeX && y == pattRangeY ){
				return true;
			}
		}
		return false;
	}

	private boolean isSurvive(int x, int y, int index){
		if(index == sp.length){
			return true;
		}
		if(isOutRange(x) || isOutRange(y)){
			return false;
		}

		if(! isRangeSP(x, y, index)){
			return false;
		}
		else{
			for(int i=0; i < pyonRange.length;i++){
				boolean ans = isSurvive(x + pyonRange[i][0], y + pyonRange[i][1], index + 1 );
				if(ans)
					return true;
			}
			return false;
		}

	}

	public void doIt(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int startx = sc.nextInt();
			int starty = sc.nextInt();
			if(startx == 0 && starty == 0)
				break;
			int n = sc.nextInt();
			sp = new int[n][10];
			for(int i=0; i < n; i++){
				sp[i][0] = sc.nextInt();
				sp[i][1] = sc.nextInt();
			}
			boolean ans = false;
			for(int i=0; i < pyonRange.length; i++){
				ans = isSurvive(startx + pyonRange[i][0], starty + pyonRange[i][1], 0);
				if(ans){
					break;
				}
			}

			if(ans){
				System.out.println("OK");
			}
			else{
				System.out.println("NA");
			}
		}
	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;

const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

void pushHeap(vector<int>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}

int popHeap(vector<int>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  int i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}

vector<int> ver;
void dfs(const graph &g,int v){
  ver[v]=1;
  for(auto i:g[v]){
    if(ver[i]!=1)continue;
    dfs(g,i);
  }
}

int binary_search(vector<int> v,int key){
  int left=0,right=v.size()-1;
  if(v.empty())return -1;
  while(abs1(right-left)>1){
    int mid=left+(right-left)/2;
    if(v[mid]<key)left=mid;
    else right=mid;
  }
  return left;
}

int main(){
  int i,j,k,cnt=0;
  string s;
  cin>>s;
  int n=s.size();
  int b[26];
  for(i=0;i<26;i++)b[i]=0;
  for(i=0;i<n;i++){
    b[s[i]-'a']++;
  }
  int c[n];
  for(i=0;i<n;i++){
    b[s[i]-'a']--;
    c[i]=n-i-1-b[s[i]-'a'];
  }
  ll d[n];
  for(i=0;i<n;i++)d[i]=0;
  d[0]=1;
  for(i=1;i<n;i++){
    d[i]=d[i-1]+c[n-i-1];
  }
  cout<<d[n-1]<<endl;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll INF = LLONG_MAX;
constexpr double DINF = DBL_MAX;
constexpr double PI = M_PI;
 
int main(){
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
 
  long long n;
  cin >> n;
  vector<ll> vec(n);
  vector<double>  x(n), y(n);
  for(int i = 0; i < n; i++){
    vec[i] = i;
    cin >> x[i] >> y[i];
  }
  double ans = 0;
  do{
    for(int i = 0; i < n-1; i++){
      int j = vec[i], k = vec[i+1];
      ans += sqrt((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k]));
    }
  }while(next_permutation(vec.begin(), vec.end()));
  for(int i = 1; i <= n; i++){
    ans /= i;
  }
  printf("%.10f\n", ans);
  return 0;
}

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

public class Main {

    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(in.readLine());
            StringTokenizer st = new StringTokenizer(in.readLine());
            int tallest = 0;
            int res = 0;
            for (int i = 0; i < n; i++) {
                int x = Integer.parseInt(st.nextToken());
                if (x >= tallest) {
                    tallest = Math.max(tallest, x);
                    res++;
                }
            }
            System.out.println(res);
        } catch (IOException ex) {

        }
    }

}

Measured memory_bytes: 23124
#include <sys/time.h>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <cctype>

using namespace std;

using ll = long long;
using P = pair<double, double>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
ll mod = 1000000007LL;



int main() {
	int h,w,k;
	cin >> h >> w >> k;

	vector<string> cs(h);

	rep(y, h) {
		cin >> cs[y];
	}
	int ans = 0;

	rep(i, 1 << w) {
		//cout << "i:" << i << endl;
		vector<string> ch = cs;
		int cur = i;
		int index_w = 0;
		while(cur > 0) {
			if ((cur & 1) == 1) {
				rep(y, h) {
					ch[y][index_w] = '+';
				}
			}
			cur = cur >> 1;
			index_w++;
		}

		rep(j, 1 << h) {
			//cout << "j:" << j << endl;

			int count = 0;
			int cur_h = j;
			int index_h = 0;
			while(cur_h > 0) {
				if ((cur_h & 1) == 1) {
					rep(x, w) {
						//cout << ch[index_h][x];
						if (ch[index_h][x] == '#') {
							count++;
						}
					} 
					//cout << endl;
				}
				cur_h = cur_h >> 1;
				index_h++;
			}
			//cout << "count: " << count << endl;
			if (count == k) {
				ans++;
			}
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3188
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int ll

const int N = 3000 + 10 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

int a[N][N];
int dp[N][N][4];

void solve() {
    int r , c , k;
    cin >> r >> c >> k;
    for(int i = 1; i <= k; i ++) {
        int x, y , v;
        cin >> x >> y >> v;
        a[x][y] = v;
    }
    for(int i = 1; i <= r; i ++) {
        for(int j = 1; j <= c; j ++) {
            dp[i][j][0] = max({dp[i - 1][j][1], dp[i - 1][j][2], dp[i - 1][j][3]});
            dp[i][j][1] = max(max({dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j][2], dp[i - 1][j][3]}) + a[i][j], max(dp[i][j - 1][1], dp[i][j - 1][0] + a[i][j]));
            for(int k = 2; k <= 3; k ++) {
                dp[i][j][k] = max(dp[i][j - 1][k] , dp[i][j - 1][k - 1] + a[i][j]);
            }
        }
    }
    cout << max(dp[r][c][1] , max(dp[r][c][2] , dp[r][c][3]));
}

/*
1 1 5 5
1 2 13
*/
main() {
    ios;
    int tt = 1;
   // cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 356260
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define ceil(n, m) ((n / m) + ( n % m ? 1 : 0))
#define fast_IO  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file_in freopen("input.txt","r",stdin);
#define file_out freopen("output.txt","w",stdout);
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

int main(){
    //fast_IO;

    string s;
    cin >> s;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='B'){
            s[i]=' ';
            bool f = 1;
            for(int j=i-1;j>=0 && f;j--){
                    if(s[j]!=' ')
                        s[j] = ' ',f=0;
            }
        }
    }
    for(int i=0;i<(int)s.size();i++)
        if(s[i]!=' ') cout<<s[i];
    return 0;
}


Measured memory_bytes: 3576
//
// Created by sposa on 19.09.2020.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    char st[1000];
    char s = 's';
    char s1='e';

    scanf("%s",&st);

    if(st[strlen(st)-1]!= 's'){
        strncat(st,&s, 1);
    }
    else{
        strncat(st,&s1,1);
        strncat(st,&s,1);
    }
    printf("%s",st);

    return 0;
}



Measured memory_bytes: 2148
#include <stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{   int a[200];
int i,x,sum=0;
    scanf("%d",&x); 
	for(i=0;i<x;i++)
	scanf("%d",&a[i]);
    sort(a,a+x);
	for(int i=1;i<x;i++)
		sum+=a[i]-a[i-1];
	printf("%d\n",sum);

}

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;

int main() {
  ll K, N;
  cin >> N >> K;
  vector<ll> v(N);
  for(ll i = 0LL; i < N; i++) {
    cin >> v.at(i);
  }
  ll M=0LL;
  ll MM=0LL;
  for(ll i = 0LL; i < K; i++) {
    M += v.at(i);
  }
  MM=M;
  ll p = 0LL;
  for(ll i = 0LL; i < N-K;i++){
    M+=v.at(K+i) - v.at(i);
    chmax(MM,M);
  }
  cout << fixed << setprecision(10);
  cout<<(double)(K+MM)/2LL << endl;
}
    

Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val N = readInputLine().toInt()

    var rank = 1

    while (true) {
        val num = rank * (rank + 1) / 2
        if (num == N) {
            break
        }
        if (num > N) {
            println("No")
            return
        }
        rank++
    }

    println("Yes")
    println(rank + 1)

    val ans = Array(rank + 1) { mutableListOf<Int>() }

    var top = 0
    var btm = 1

    for (i in 1..N) {
        ans[top].add(i)
        ans[btm].add(i)

        if (ans[top].size == rank) {
            top++
            btm = top + 1
        } else {
            btm++
        }
    }

    for (i in 0..rank) {
        println("$rank ${ans[i].joinToString(" ")}")
    }
}

fun readInputLine(): String {
    return readLine()!!
}


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

using namespace std;

int main()
{
	string n;
	cin >> n;
	
	for(int i = 0; i < 3; i++) {
		if(n[i] == '1') {
			cout << 9;
		}
		else {
			cout << 1;
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
    int n;
    cin >> n;
    cout << n/3 << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps DBL_EPSILON
#define mod (ll)1000000007
#define INF INT_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
signed main() {
	int a, b;
	cin >> a >> b;
	cout << max({ a + b,a - b,a * b }) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

// vectorの重複削除
// std::sort(test.begin(), test.end());
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //
// const int MOD = 1000000007;
// string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// printf("%.20f\n", ans); あれ
// const double PI = 3.141592653589793238462643383;

int main() {
  int p,q,r; cin>>p>>q>>r;
  cout << p+q+r - max({p,q,r}) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DBP
#define deb(...) fprintf(stderr,__VA_ARGS__)
#else
#define deb(...) 0
#endif
#define fst first
#define snd second
#define fore(x,a,b) for(int x=(a), qwerty=(b); x<qwerty; x++)
#define pb push_back
#define mset(a,v) memset((a),(v),sizeof(a))
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) int((a).size())
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

const ll MOD=1e9+7;
ll add(ll a, ll b){
  a+=b;
  if(a>=MOD)a-=MOD;
  return a;
}
ll sub(ll a, ll b){
  a-=b;
  if(a<0)a+=MOD;
  return a;
}
ll mult(ll a, ll b){return (a*b)%MOD;}

const int N=2e5+5;
int n, C[N];
ll tmp[N], tmp2[N];
//1 2 1 2 2
int main(){FIN;
  cin >> n;
  fore(x,0,n)cin>>C[x];
  tmp2[0]=1;tmp[C[n-1]]=1;tmp2[n-1]=1;
  for(int x=n-2; x>=0; x--){
    if(C[x]!=C[x+1])tmp[C[x]]=add(tmp2[x+1],tmp[C[x]]);
    tmp2[x] = tmp[C[x]];
  }
  cout << tmp2[0] << "\n";
}

Measured memory_bytes: 4224
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
li = sorted(rl(), reverse=True)
a = 0
b = 0
for i in range(n):
  if i & 1 == 0:
    a += li[i]
  else:
    b += li[i]
print(a-b)



Measured memory_bytes: 26960
n = gets.to_i
s = []
rsl = [0,0,0,0]
rsllabel = ["AC","WA","TLE","RE"]
n.times do
  s << gets.chomp
end
s.size.times do |i|
  rsl[rsllabel.find_index(s[i])] += 1
end
rsl.size.times do |i|
  puts "#{rsllabel[i]} x #{rsl[i]}"
end

Measured memory_bytes: 20784
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include <numeric>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 9999999

using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };


ll m = 1000000007;

ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}


string s;
ll K;
int main() {

	cin >> s;
	cin >> K;

	ll l = s.length();
	string ans = "";


	REP(i, l) {

		int c = s[i] - 'a';
		int rem = (26 - c)%26;

		if (i == l - 1) {
			char a = 'a' + (c + K) % 26;
			ans += a;
			break;
		}

		if (K >= rem) {
			ans += "a";
			K -= rem;
		}
		else ans += s[i];
	}

	cout << ans << endl;

}

Measured memory_bytes: 768
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
n=int(input())
z=[]
#check=[0]*(n+1)
p=factorization(n) 
sum=0
if n==1:
    print(0)
    exit()
else:
    for pair in p:
        for i in range(pair[1]):
            z.append(pair[0]**(i+1))
            
#print(z)
while True:
    now=z.pop(0)
    if n>=now and n%now==0:
        sum+=1

        n=n/now
    if len(z)==0:
        break
print(sum)


Measured memory_bytes: 63444
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			String in = br.readLine();
			String chr[] = in.split(" ");
			int a = Integer.parseInt(chr[0]);
			int b = Integer.parseInt(chr[1]);
			System.out.println(a%3==0||b%3==0||(a+b)%3==0?"Possible"
							   :"Impossible");

		}
	}
}


Measured memory_bytes: 25340
#include <algorithm>

namespace rika
{
  template <typename T>
  class edge
  {
  public:
    int to;
    T cost;
    
    edge() = default;
    edge(const edge<T>&) = default;
    edge(edge<T>&&) = default;
    edge& operator =(const edge<T>&) = default;
    edge& operator =(edge<T>&&) = default;

    ~edge() = default;

    edge(int _to, T _cost) : to(_to), cost(_cost) {}
  };
}
  int N;

#include<bits/stdc++.h>
using namespace std;
using namespace rika;
namespace rika
{
  namespace internal
  {
    template <typename TValue, typename TGraph>
    std::pair<TValue, int> visit(int from, int v, const TGraph &g)
    {
      if(v >= N)
        throw "test";
      auto r = std::make_pair(TValue(), v);
      try{
      for(auto it = g[v].begin(); it != g[v].end(); ++it)
      {
        if(it->to == from)
          continue;
        auto r2 = visit<TValue>(v, it->to, g);
        if(r2.first + it->cost >= r.first)
          r = std::make_pair(r2.first + it->cost, r2.second);
      }
      }catch(const std::out_of_range &e){throw "test";}
      return r;
    }
  }

  template <typename TValue, typename TGraph>
  TValue tree_diameter(const TGraph &g)
  {
    using namespace internal;
    auto r1 = visit<TValue>(-1, 0, g);
    auto r2 = visit<TValue>(-1, r1.second, g);
    return r2.first;
  }
}

#include<bits/stdc++.h>
using namespace std;
using namespace rika;
int main()
{
  cin >> N;
  vector<vector<edge<int>>> g(N * 10);
  for(int i = 0; i < N - 1; i++)
  {
    int s, t, w;
    cin >> s >> t >> w;
    g[s].push_back(edge<int>(t, w));
    g[t].push_back(edge<int>(s, w));
  }
  cout << tree_diameter<int>(g) << endl;
}

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


void solve() {
  int N;
  scanf("%d", &N);
  string s;
  cin >> s;
  if (N>=3200) {
    std::cout << s << '\n';
  } else{
    std::cout << "red" << '\n';
  }

}

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


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

int main(){
  constexpr char block= '#';
  int H,W,K;
  cin >> H >> W >> K;

  vector<string> board(H);
  for(int h=0; h<H; h++){
    cin >> board.at(h);
  }

  vector<vector<int>> pos_col(H); // 番兵(W)付き
  vector<vector<int>> numbers(H); // 各ブロックに対応する番号
  vector<int> pos_row;            // 番兵(H)付き

  int cnt= 1;
  for(int h=0; h<H; h++){
    for(int w=0; w<W; w++){
      if(board.at(h).at(w)==block){
        pos_col.at(h).emplace_back(w);
        numbers.at(h).emplace_back(cnt);
        cnt++;
      }
    }
    if(!pos_col.at(h).empty()){
      pos_col.at(h).emplace_back(W);
      pos_row.emplace_back(h);
    }
  }
  pos_row.emplace_back(H);

  for(size_t i=0; i<pos_row.size(); i++){
    if(i==0){
      for(int h=0; h<pos_row.at(0); h++){
        for(size_t j=0; j< pos_col.at(pos_row.at(0)).size(); j++){
          if(j==0){
            for(int w=0; w< pos_col.at(pos_row.at(0)).at(0); w++){
              cout << numbers.at(pos_row.at(0)).at(0) <<" ";
            }
          }
          else{
            for(int w=pos_col.at(pos_row.at(0)).at(j-1); w<pos_col.at(pos_row.at(0)).at(j); w++){
              cout << numbers.at(pos_row.at(0)).at(j-1) <<" ";
            }
          }
        }
        cout << endl;
      }
    }
    else{
      for(int h=pos_row.at(i-1); h<pos_row.at(i); h++){
        for(size_t j=0; j< pos_col.at(pos_row.at(i-1)).size(); j++){
          if(j==0){
            for(int w=0; w< pos_col.at(pos_row.at(i-1)).at(0); w++){
              cout << numbers.at(pos_row.at(i-1)).at(0) <<" ";
            }
          }
          else{
            for(int w=pos_col.at(pos_row.at(i-1)).at(j-1); w<pos_col.at(pos_row.at(i-1)).at(j); w++){
              cout << numbers.at(pos_row.at(i-1)).at(j-1) <<" ";
            }
          }
        }
        cout << endl;
      }
    }
  }
}

Measured memory_bytes: 4860
a,b=map(int,input().split())

list=[2,3,4,5,6,7,8,9,10,11,12,13,1]
# print(list.index())

a_val=list.index(a)
b_val=list.index(b)

if a_val>b_val:print('Alice')
elif a_val<b_val:print('Bob')
else:print('Draw')

Measured memory_bytes: 3060
def sol():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[]
    d={}
    x=y=0
    for i in range(n):
        t=int(input())
        a.append(t)
        if t in d:
            d[t]+=1
        else:
            d[t]=1
        if t>x:
            y=x
            x=t
        elif t>y:
            y=t
    for i in a:
        if i==x and d[i]==1:
            print(y)
        else:
            print(x)

if __name__=="__main__":
    sol()

Measured memory_bytes: 65616
S = int(input())

if(S < 3):
    print(0)
    exit()

if(S < 6):
    print(1)
    exit()

div_S = S // 3

ans = 1

suuretu = [1 for _ in range(2000)]
suuretu.insert(0, 0)

for i in range(1,div_S):
    ruisekiwa = [0]
    for j in suuretu[1:]:
        ruisekiwa.append((ruisekiwa[-1] + j) % (10**9+7))

#    print(ruisekiwa[:20])
    ans = (ans +ruisekiwa[S - 2 - i * 3]) % (10**9 + 7)

#    print(ruisekiwa)
#    print(len(ruisekiwa))
    suuretu = ruisekiwa

print(ans)

Measured memory_bytes: 9220