akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

int main() {
    int N, M;
    cin >> N >> M;
    vector<pii> ab(N);
    for (int i = 0; i < N; i++) {
        cin >> ab[i].first >> ab[i].second;
    }
    sort(ab.begin(), ab.end());
    ll cost = 0;
    ll remain = M;
    for (int i = 0; i < N; i++) {
        ll buy = min(remain, ab[i].second);
        cost += ab[i].first * buy;
        remain -= buy;
        if (remain == 0) break;
    }
    cout << cost << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 1000000007

int n, m;
ll x[100010], y[100010];

int main(){
	while(scanf("%d %d", &n, &m)!=EOF){
		ll sum = 0, sum2 = 0;
		for(int i=0; i<n; i++){
			scanf("%lld ", &x[i]);
			sum = (sum + x[i]*((ll)i))%MOD;
			sum = (sum - x[i]*((ll)n-i-1))%MOD;
		}
		for(int i=0; i<m; i++){
			scanf("%lld ", &y[i]);
			sum2 = (sum2 + y[i]*((ll)i))%MOD;
			sum2 = (sum2 - y[i]*((ll)m-i-1))%MOD;
		}
		printf("%lld\n", (sum*sum2)%MOD);
	}
	return 0;
}

Measured memory_bytes: 1792
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();

        int res = 0;
        for (int a=0; a<=A; a++) {
            for (int b=0; b<=B; b++) {
                int c = (X - a * 500 - b * 100) / 50;
                if (c >= 0 && c <= C)
                    res++;
            }
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 22608
import sys


def parse(n):
    temp = 0
    digit = 1
    for c in n:
        if c == 'm':
            temp += digit * 1000
            digit = 1
        elif c == 'c':
            temp += digit * 100
            digit = 1
        elif c == 'x':
            temp += digit * 10
            digit = 1
        elif c == 'i':
            temp += digit
            digit = 1
        else:
            digit = int(c)
    return temp

def transform(n):
    temp = ''
    key = ['i', 'x', 'c', 'm']
    for i in xrange(3, -1, -1):
        digit = n / (10**i)
        if digit > 0:
            temp += '' if digit == 1 else str(digit)
            temp += key[i]
            n %= 10**i
    return temp


n = int(sys.stdin.readline())
for z in xrange(n):
    a, b = sys.stdin.readline().split()
    print transform(parse(a) + parse(b))

Measured memory_bytes: 4256
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Tree = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;

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

	VecVec c(10, Vec(10));

	repn(i, n){
		string s = to_string(i);
		ll a = s[0]-'0', b = s[s.size()-1]-'0';
		c[a][b]++;
	}

	ll ans = 0;
	rep(i, 10){
		rep(j, 10) ans += c[i][j]*c[j][i];
	}
	co(ans);

	return 0;
}


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

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;

  int cnt = 0;
  for (int i = 0; i <= n; ++i) {
    if (s[i] == '0') {
      cnt = 0;
    } else {
      cnt++;
    }
    if (cnt >= m) {
      puts("-1");
      return 0;
    }
  }
  
  int cur = n;
  vector<int> ans;
  while (cur > 0) {
    int next = max(0, cur - m);
    while (s[next] == '1') next++;
    ans.push_back(cur - next);
    cur = next;
  }

  for (int i = ans.size() - 1; i >=0; --i) {
    cout << ans[i];
    if (i > 0) cout << " ";
  }
  puts("");
  return 0;
}



Measured memory_bytes: 1144
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr usize operator"" _z(unsigned long long x) noexcept {
  return static_cast<usize>(x);
}

class rep {
  const usize f, l;

public:
  class itr {
    friend rep;
    usize i;
    constexpr itr(const usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
  constexpr itr begin() const noexcept { return itr(f); }
  constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
  const usize f, l;

public:
  class itr {
    friend revrep;
    usize i;
    constexpr itr(usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
  constexpr itr begin() const noexcept { return itr(l); }
  constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
  return a < b ? b - a : a - b;
}
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>


namespace n91 {

void main_() {
  const std::string s = scan<std::string>();
  const std::string t = scan<std::string>();
  usize ans = 0_z;
  for (const auto i : rep(0_z, s.size())) {
    if (s[i] == t[i]) {
      ++ans;
    }
  }
  std::cout << ans << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


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

public class Main{
	static void main() throws Exception{
		int n=sc.nextInt();
		int[][]in=new int[n][2];
		for(int i=0;i<n;i++)in[i]=sc.intArr(2);
		for(int i=0;i+2<n;i++) {
			boolean ok=true;
			for(int j=i;j<i+3;j++) {
				ok&=(in[j][0]==in[j][1]);
			}
			if(ok) {
				pw.println("Yes");
				return;
			}
		}
		pw.println("No");
	}
	public static void main(String[] args) throws Exception {
		sc = new MScanner(System.in);
		pw = new PrintWriter(System.out);
//		int tc = 1;
//		tc=sc.nextInt();
//		while (tc-- > 0)
			main();
		pw.flush();
	}

	static PrintWriter pw;
	static MScanner sc;

	static class MScanner {
		StringTokenizer st;
		BufferedReader br;

		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int[] intArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}

		public long[] longArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}

		public int[] intSortedArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

		public long[] longSortedArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

		public Integer[] IntegerArr(int n) throws IOException {
			Integer[] in = new Integer[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}

		public Long[] LongArr(int n) throws IOException {
			Long[] in = new Long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}

	static void shuffle(int[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			int tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}

	static void shuffle(long[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			long tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}
}

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

int main(){
    int a, b;
    cin >> a >> b;
    if(a <= b){
        cout << 0 << endl;
    }else if(a/b < 2){
        cout << 0 << endl;
    }else{
        cout << a - b * 2 << endl;
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <assert.h>
#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;





// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main(){
    string s;
    cin >> s;
    map<char,int> seen;
    rep(i,s.size()){
        seen[s[i]]++;
    }
    map<char,int>::iterator it;
    it = seen.begin();
    while(it!=seen.end()){
        if (seen[(*it).first]%2==1){
            cout << "No"; rn 0;
        }
        it++;
    }
    cout << "Yes";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <string>

using namespace std;

int main()
{
    int n;
    long int a;

    cin >> n;

    cin >> a;
    long int total = a;

    for(int i = 1; i < n; i++){
        cin >> a;
        long int tmp = total * a;
        if(a ==0){
            total = 0;
            break;
        }
        if (tmp > 1000000000000000000 || total > tmp){
            total = -1;
        }
        else{
            total = tmp;
        }
    }

    cout << total << endl;

    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rpd(i,a,b) for(register int i=a;i>=b;--i)
#define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
typedef long long ll;
const int N=100+5;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int main(){
	n=read();
	if(n%2==0)return puts("0.5000000000"),0;
	printf("%.10lf\n",(0.5*(n+1))/(1.0*n));
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		sc.close();
		if(H == 1 || W == 1) {
			System.out.println(1);
			return;
		}
		long h = (H + 1) / 2;
		long w = (W + 1) / 2;
		long h2 = W / 2; 
		long w2 = H / 2;
		System.out.println((long)(h * w) + (long)(h2 * w2));
	}
}


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

int main(){
    int n;
    int theirboss[200000];
    int theirsub[200000];
    cin >> n;
    
    for(int i = 0; i < n-1; i++){
        cin >> theirboss[i];
        theirsub[i] = 0;
    }
    theirsub[n-1] = 0;

    
    for(int i = 0; i < n; i++){
        theirsub[ theirboss[i]-1 ]++;
    }

    for(int i = 0; i < n; i++){
        cout << theirsub[i] <<endl;
    }

    
}

Measured memory_bytes: 5152
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")  */
#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair

#define pss pair<line*, line*>
 
using namespace std;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
                                 
const ll inf = 1e18;
const int MOD = 1e9 + 7;

const int dx[] = {-1, +1, -2, +2, -2, +2, -1, +1};
const int dy[] = {-2, -2, -1, -1, +1, +1, +2, +2};

const int N = 5e5 + 5;

ll dp[105][N];   

int main() {                
#ifdef Mask                                                         
  freopen(".in", 	"r", stdin);
  freopen(".out", "w", stdout);  
#endif
	ios_base :: sync_with_stdio(false);               
  cin.tie(nullptr); 	
  int n, W;
  cin >> n >> W;
  ll w[n + 1], c[n + 1];
  for (int i = 1; i <= n; i++) {
   	cin >> w[i] >> c[i];
  }
  for (int i = 0; i < n; i++) 
   	for (int k = 0; k < N; k++)
   		dp[i][k] = 1e18;
  dp[0][0] = 0; 
  for (int i = 0; i < n; i++) {
   	for (int k = 0; k < N; k++) 
   	 	dp[i + 1][k] = dp[i][k];
   	for (int k = 0; k < N; k++) 
   		dp[i + 1][k + c[i + 1]] = min(dp[i + 1][k + c[i + 1]], dp[i][k] + w[i + 1]);
  }
  ll ans = 0;
  for (int i = 0; i < N; i++)
  	if (dp[n][i] <= W)
  		ans = max(ans, i * 1ll);
  cout << ans;
	return 0;   
}



Measured memory_bytes: 395520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll l, r;
    cin >> l >> r;
    ll mn = 1e8;
    for (ll i = l; i <= min(r, l + 2019); i++) {
        for (ll j = i + 1; j <= min(r, l + 2019); j++) {
            mn = min(mn, (i * j) % 2019);
        }
    }
    cout << mn;
    return  0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const long long mod = 1000000007LL;

ll a[23][23];
ll dp[1<<21];
ll bitcnt[1<<21];

int main() {
  int n;
  cin >> n;
  rep(i,n)rep(j,n) cin >> a[i][j];
  dp[0] = 1;
  for(int s = 1; s < (1<<n); s++) {
    bitcnt[s] = bitcnt[s/2] + s%2;
    rep(l,n) {
      if(s>>l&1) {
        dp[s] += dp[s - (1<<l)] * a[bitcnt[s] - 1][l];
        dp[s] %= mod;
      }
    }
  }
  cout << dp[(1<<n) - 1] << endl;
  return 0;
}

Measured memory_bytes: 33024
import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int dp[][]=new int[3][n];
		for(int i=0;i<n;i++)
		{
			if(i==0)
			{
				dp[0][0]=in.nextInt();
				dp[1][0]=in.nextInt();
				dp[2][0]=in.nextInt();
			}
			else
			{
				dp[0][i]=Math.max(dp[1][i-1], dp[2][i-1])+(in.nextInt());
				dp[1][i]=Math.max(dp[0][i-1], dp[2][i-1])+(in.nextInt());
				dp[2][i]=Math.max(dp[0][i-1], dp[1][i-1])+(in.nextInt());
			}
		}
		System.out.println(Math.max(dp[0][n-1], Math.max(dp[1][n-1], dp[2][n-1])));
	}
}


Measured memory_bytes: 91868
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

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

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 5010

int sum[SIZE][SIZE];

int main(){
  int N, M, x[SIZE], y[SIZE];
  vector<int> vecX, vecY;
  map<int,int> dicX, dicY;

  scanf("%d%d", &N, &M);

  for (int i=0; i<N; i++) {
    scanf("%d%d", x+i, y+i);
    vecX.push_back(x[i]);
    vecY.push_back(y[i]);
  }

  vecX.push_back(-INF-10);
  vecY.push_back(-INF-10);

  sort(vecX.begin(), vecX.end());
  vecX.erase(unique(vecX.begin(), vecX.end()), vecX.end());
  sort(vecY.begin(), vecY.end());
  vecY.erase(unique(vecY.begin(), vecY.end()), vecY.end());

  for (int i=0; i<vecX.size(); i++) dicX[vecX[i]] = i;
  for (int i=0; i<vecY.size(); i++) dicY[vecY[i]] = i;

  for (int i=0; i<N; i++) {
    sum[dicX[x[i]]][dicY[y[i]]]++;
  }

  for (int i=0; i<=N; i++)
    for (int j=0; j<=N; j++)
      sum[i+1][j] += sum[i][j];

  for (int i=0; i<=N; i++)
    for (int j=0; j<=N; j++)
      sum[i][j+1] += sum[i][j];

  for (int i=0; i<M; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

    x1 = lower_bound(vecX.begin(), vecX.end(), x1) - vecX.begin();
    y1 = lower_bound(vecY.begin(), vecY.end(), y1) - vecY.begin();
    x2 = lower_bound(vecX.begin(), vecX.end(), x2+1) - vecX.begin() - 1;
    y2 = lower_bound(vecY.begin(), vecY.end(), y2+1) - vecY.begin() - 1;

    int ans = sum[x1-1][y1-1] + sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1];

    printf("%d\n", ans);
  }

  return 0;
}



Measured memory_bytes: 101680
n, m = map(int, input().split())
alst = [input() for _ in range(n)]
blst = [input() for _ in range(m)]

for i in range(n - m + 1):
    for j in range(n - m + 1):
        for k, row in enumerate(blst):
            if alst[i + k][j:j + m] == blst[k]:
                continue
            break
        else:
            print("Yes")
            exit()
print("No")

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

using ll = long long;
using namespace std;

int main()
{
  int N; cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    A[i] -= i + 1;
  }

  sort(A.begin(), A.end());

  ll median = A[N/2];
  ll ans = 0;
  for (ll i = 0; i < N; ++i) {
    ans += abs(A[i] - median);
  }

  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
        long long int i,j=0,che=0,ans=0;
        char cent;
        char c[100000];
        string s;
        map<char,int> cou;
        cin >> s;
        for(i=0;i<s.size();i++){
                if(s[i]!='x'){
                        cou[s[i]]++;
                        c[j] = s[i];
                        j++;
                }
        }
        for(i=0;i<j;i++){
                if(cou[c[i]] == 1){
                        che++;
                        cent=c[i];
                        //cout << cent << endl;
                        //return 0;
                }
                /*if(che == 2){
                        cout << -1 << endl;
                        return 0;*/
                //}
        }
        //che = s.find(cent);
        /*for(i=che;i<size();i++){
                if(s[che+i]!=s[che-i]){
                        if(s[che+i] == 'x'){
                                s.insert(s.begin()+che-i, 'x');
                        }else s.insert(s.begin()+che+i, 'x');
                        i--;
                }
        }
        cout << s << endl;*/
        i=0;j=s.size()-1;
        while(i<j){
                if(s[i]!=s[j]){
                        if(s[i]!='x' && s[j]=='x'){
                                ans++;
                                j--;
                        }else if(s[j]!='x' && s[i] == 'x'){
                                ans++;
                                i++;
                        }else if(s[i] != 'x' && s[j] != 'x'){
                                cout << -1 << endl;
                                return 0;
                        }
                        continue;
                }
                i++;
                j--;
        }
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 512
N=int(input())
C=[0]*(N-1)
S=[0]*(N-1)
F=[0]*(N-1)
for i in range(N-1):
    C[i],S[i],F[i]=map(int,input().split())
for i in range(N-1):
    t=0
    for j in range(N-i-1):
        if S[j+i]>=t:
            t=S[j+i]+C[j+i]
        else:
            if t%F[j+i]==0:
                t=t+C[j+i]
            else:
                t=t+(F[j+i]-(t%F[j+i]))+C[j+i]
    print(t)
print(0)

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

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	map<char, char> m;
	for (int i = 0; i < s.length(); i++) {
		char &c = m[s[i]];
		if (c&&c != t[i]) {
			cout << "No" << endl;
			return 0;
		}
		c = t[i];
	}
	m.clear();
	swap(s, t);
	for (int i = 0; i < s.length(); i++) {
		char &c = m[s[i]];
		if (c&&c != t[i]) {
			cout << "No" << endl;
			return 0;
		}
		c = t[i];
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 776
import sys
# import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k = map(int, readline().split())
p = list(map(int, readline().split()))

tmp = [(i+1)/2 for i in p]
# cs = list(np.cumsum(tmp))

cs = [0]*n
cs[0] = tmp[0]
for i in range(len(tmp)-1):
    cs[i + 1] = cs[i] + tmp[i + 1]

if n == k:
    print(cs[-1])
    exit()
ans = 0
for i in range(n - k):
    ans = max(ans, cs[i + k] - cs[i])
print(ans)

Measured memory_bytes: 32532
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <list>
#include <string>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <climits>
#include <map>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	long long int ans=k;
	k--;
	for (int i = 1; i < n; i++)
	{
		ans *= k;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;


int main() {
	ll x = 1;
	ll y = 1;
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		ll a, b;
		cin >> a >> b;
		ll k = max((x + a - 1) / a, (y + b - 1) / b);
		x = k * a;
		y = k * b;
	}
	cout << x + y << "\n";
	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define INF_LL 1e18
#define INF 1e9

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()

#define fst first
#define snd second

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int dp[2020][2020][2] = {};
int main(void){
	int N, M;
	string s, t;
	cin >> M >> N;
	cin >> s >> t;

	REP(i, M+1){
		REP(j, N+1){
			dp[i][j][0] = -INF;
			dp[i][j][1] = 0;
		}
	}

	REP(i, M+1){
		REP(j, N+1){
			if(i < M){
				if(s[i] == 'I'){
					dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1]+1);
				}else{
					dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0]+1);
				}
			}
			if(j < N){
				if(t[j] == 'I'){
					dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][1]+1);
				}else{
					dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][0]+1);
				}
			}
		}
	}
	int res = 0;
	REP(i, M+1){
		REP(j, N+1){
			res = max(res, dp[i][j][0]);
		}
	}

	cout << res << endl;
}

Measured memory_bytes: 34688
#include<bits/stdc++.h>
#define re register
long long f[510][510],a[510][510];
long long sc(re int x1,re int y1,re int x,re int y)
{
	if(!x1||!y1)return 0;
	if(!x)x=1;if(!y)y=1;
	return a[x1][y1]-a[x-1][y1]-a[x1][y-1]+a[x-1][y-1];
}
int main()
{
	re int n;
	scanf("%d",&n);
	for(re int i=1;i<=n;i++)
		for(re int j=1;j<=n;j++)if(i!=j)scanf("%lld",&a[i][j]);
	for(re int i=1;i<=n;i++)
		for(re int j=1;j<=n;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	f[0][0]=0;
	for(re int i=0;i<=n;i++)
	{
		for(re int j=i;j<=n;j++)if(i!=0||j==0)
		{
			re long long x1=0;
			for(re int i1=j+1;i1<=n;i1++)
			{
				x1+=sc(j,i1,1,i1)+sc(i1,i1-1,i1,i);
				f[j+1][i1]=std::max(f[j+1][i1],f[i][j]+x1);
				//printf("**%d %d %lld %lld %lld %lld\n",j+1,i1,x1,f[j+1][i1],a[2][1],a[1][1]);
			}
		}
	}
	re long long ans=0;
	for(re int i=1;i<=n;i++)ans=std::max(ans,f[i][n]);
	printf("%lld\n",a[n][n]-ans);
}

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

using namespace std;


#define ss second
#define ff first
#define int long long
//#define double long double
#define pb push_back

const int N = 1e6 + 1, MOD = 1e9 + 7, mod = 998244353, INF = 3e18;

mt19937 Flash_new_51(51515);

using vi = vector <int>;
using vp = vector <pair <int, int>>;


bool used[N];

signed main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);
   int A, B, C, K;
   cin >> A >> B >> C >> K;
      A-= B;
   if (K % 2 == 1) A*= -1;
   cout << A;

}

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

int main() {
  string c;
  cin >> c;
    if ( c == "a"){
      cout << "vowel" << endl;
    }
  else  if ( c == "i"){
      cout << "vowel" <<endl;
    }
  else if ( c == "u") {
    cout << "vowel" <<endl;
  }
  else if ( c == "e"){
    cout << "vowel" <<endl;
  }
  else if ( c== "o"){
    cout << "vowel" <<endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

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

int main() {
    int n; cin >> n;
    int x[n], y[n], h[n];
    int xt, yt, ht;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> h[i];
        if(h[i] > 0) {
            xt = x[i], yt = y[i];
            ht = h[i];
        }
    }

    int cx, cy, H;
    for (cx = 0; cx <= 100; cx++)
    {
        for (cy = 0; cy <= 100; cy++)
        {
            H = ht + abs(xt - cx) + abs(yt - cy);
            bool ok = true;
            for (int i = 0; i < n; i++)
            {
                if(h[i] != max(H - abs(x[i] - cx) - abs(y[i] - cy), 0)) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }

    }

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 1000000;
int N;
ll A[Nmax];

int main(){
	cin >> N;
	for(int i=0; i<N; i++) cin >> A[i];
	sort(A,A+N);

	int possible = 0;
	ll sum = A[0];
	for(int i=1; i<N; i++){
		if(2*sum < A[i]){
			possible = i;
		}
		sum += A[i];
	}
	cout << N-possible << endl;

	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
long long int ks(int x,int n,long long int *w,long long int *v){
    long long int a[n+1][x+1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= x; j++)
        {
            if(i==0 || j==0)
            a[i][j]=0;
            else if(w[i-1]>j)
            a[i][j]=a[i-1][j];
            else a[i][j]=max(a[i-1][j], v[i-1] + a[i-1][j-w[i-1]]);
        }        
    }
    // for (int i = 0; i <= n; i++)
    // {
    //     for (int j = 0; j <= x; j++)
    //     {
    //         cout<<a[i][j]<<" ";
    //     }cout<<endl;
    // }
    return a[n][x];
}
int main(){
    long long int n,x;
    cin>>n>>x;
    long long int w[n],v[n];
    for (int i = 0; i < n; i++)
    {
        cin>>w[i]>>v[i];
    }
    long long int ans=ks(x,n,w,v);
    cout<<ans;
}

Measured memory_bytes: 79104
"use strict"
let fs = require('fs');
let input = fs.readFileSync("/dev/stdin", "utf8").split(/\s/);
console.log(
  input[0] == 'A' 
    ? 'T' 
    : input[0] == 'T'
      ? 'A'
      : input[0] == 'C'
        ? 'G'
        : 'C'):

Measured memory_bytes: 7372
#include<bits/stdc++.h>
#define FAST std::ios::sync_with_stdio(false);
#define endl '\n'
#define ll long long
#define MAXN 9999
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MAX_N 200005
#define Mem(a,b) memset(a,b,sizeof(a))
#define FREI freopen("in.txt","r",stdin)
#define FREO freopen("out.txt","w",stdout)
using namespace std;

char str[MAX_N];
int pre[30][MAX_N];

int main()
{
   //FREI;
   scanf("%s",str);
   int len=strlen(str);
   for(int i=1;i<=len;i++)
   {
      pre[str[i-1]-'a'][i]++;
      for(int j=0;j<26;j++)
         pre[j][i]+=pre[j][i-1];
   }
   ll ans=0;
   for(int i=0;i<len;i++)
   {
      ans+=(len-i-1-(pre[str[i]-'a'][len]-pre[str[i]-'a'][i+1]));
   }
   printf("%lld\n",ans+1);
   return 0;
}


Measured memory_bytes: 20864
K = int(input())
m = 7%K
ans = 1
s = set()
s.add(m)
for _ in range(K):
    #print(m)
    if m == 0:
        print(ans)
        break
    m = (m*10+7)%K
    if m in s:
        print('-1')
        break
    else:
        s.add(m)
    ans += 1

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

#define BUFSIZE 256
#define N 10
int main(void)
{
	char buf[BUFSIZE];
	int L[N];
	int v1, v2, i;
	while (fgets(buf, BUFSIZE, stdin) != NULL) {
		char *p = strtok(buf, ",");
		double t, d;
		int s, sum= 0;
		for (i = 0; i < N; ++i) {
			L[i] = atoi(p);
			sum += L[i];
			p = strtok(NULL, ",");
		}
		v1 = atoi(p);
		v2 = atoi(strtok(NULL, ","));

		t = (double)sum / (v1 + v2);
		d = v1 * t;
		s = 0;
		for (i = 0; i < N; ++i) {
			s += L[i];
			if (d <= s) { printf("%d\n", i+1); break; }
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <stdlib.h>


using namespace std;


int main(){
    int N,D;
    cin >> N >> D;
    int tmp =   D * 2 + 1;

    int ans = N / tmp;
    if(N % tmp != 0){
        ans++;
    }
    

    cout << ans << endl;
}


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

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

  string X; cin >> X;
  ll d = 0;
  ll N = X.length();
  for (ll i = 0; i < N; i++) {
    d += (X[i] - '0');
  }

  string ans = "No";
  if (d % 9 == 0) ans = "Yes";
  cout << ans << '\n';
  return 0;
}

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

long long mmax(long long a,long long b)
{
	if(a>b) return a;
	return b;
}

int main()
{
	long long a,b,n;
	cin>>a>>b>>n;
	
	if(b==1)
	{
		cout<<0<<endl;
		return 0;
	}
	
	if(n<b)
		cout<<a*n/b<<endl;
	else
	{
		long long x,maxn=0;
		for(x=b-1ll;x<=n;x+=b)
			maxn=mmax(maxn,a*x/b-a*(x/b));
		cout<<maxn<<endl;
	}
	return 0;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
int n, a[maxn];
int lo=0;
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

  cin>>n;
  for (int i=0; i<n; i++) {
    int x; cin>>x;
    if (lo+1==x) lo++;
  }
  if (lo==0) out(-1);
  cout<<n-lo<<endl;
  

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int p[2][6];

double get(double x){
	double res = 0;
	rep(i, 6){
		res += max(x * p[0][i], (1-x) * p[1][i]);
	}
	return res / 100.0;
}

void solve(){
	rep(i, 2)rep(j, 6)scanf("%d", p[i]+j);
	double low = 0, high = 1;
	rep(u, 100){
		double m1 = (low * 2 + high) / 3;
		double m2 = (low + high * 2) / 3;
		if(get(m1) < get(m2))high = m2;
		else low = m1;
	}
	printf("%.12f\n", get(low));
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

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

using namespace std;
const int N = 1e5 + 1;
typedef long long ll;
const int M = 1e9;

ll n, dp[N], h[N];

int main (){
cin >> n;
for (int i = 1;i <= n;++i){
    cin >> h[i];
}
dp[1] = 0;
dp[2] = abs (h[2]- h[1]);
for (int i = 3;i <= n;++i){
    dp[i] = min (abs(h[i - 1] - h[i]) + dp[i - 1], abs (h[i - 2] - h[i]) + dp[i - 2]);
}
cout << dp[n];
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
int main(){
    int n,x=1;
    cin >> n;
    int num[n];
    rep1(i,n) cin >> num[i];

    rep1(i,n){
        if(num[i]==x){
            x++;
        }
    }
    x--;

    x != 0 ? cout << n - x << endl : cout << -1 << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            double T = double.Parse(s[0]);
            double X = double.Parse(s[1]);

            Console.WriteLine(T / X);
        }
    }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

signed main() {
	IOS;	
	int K,ans,cnt; cin>>K;
	ans=0;
	for(int i=1;i<K+1;i++){
		for(int j=1;j<K+1;j++){
			for(int k=1;k<K+1;k++){
				cnt=gcd(i,j);
				ans+=gcd(cnt,k);
			}
		}
	}
	cout<<ans;
}


Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int n;
int a[111111];

int main(){
  ios_base::sync_with_stdio(false);

  cin >> n;
  for(int i=0;i<n;i++){
    int num;
    cin >> num;
    a[num]++; 
  }
  
  int ans = -1;
  for(int i=1;i<99999;i++){
    ans = max(ans, a[i-1]+a[i]+a[i+1]);
  }
   
  cout << ans << endl;  

  return 0;
}


Measured memory_bytes: 640
def c(h, memo):

    if h == 1:
        return 1

    if h in memo:
        return memo[h]

    num_of_attacks = 1 + c(h // 2, memo) + c(h // 2, memo)
    memo[h] = num_of_attacks
    return num_of_attacks


def main():
    
    h = int(input())
    
    memo = {}
    res = c(h, memo)
    print(res)


main()


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

using namespace std;

#define DB( x ) cout << #x << " = " << x << endl;
#define LEFT(n) (2 * (n))
#define RIGHT(n) (2 * (n) + 1)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> node;
//typedef vector <vector <ll>> matrix;

const ll INF = 1e9;
const double EPS = 1e-9;
const ll MOD = (ll)(1000000007);
const ll MAXV = (ll)(2e5 + 10);
const ll MAXE = (ll)(1e6 + 10);

ll cnt[MAXV];

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

	string s;

	cin >> s;

	vector<ll> pos_r;

	for(ll i = 0;i < s.size() - 1;i ++){
		if(s[i] == 'R' && s[i + 1] == 'L')
			pos_r.push_back(i + 1);
	}

	ll curr = 0, dif;
	for(ll i = 0;i < s.size();i ++){
		if(s[i] == 'R'){
			dif = pos_r[curr] - i;
			if(dif % 2LL == 0LL)
				cnt[pos_r[curr]] ++;
			else
				cnt[pos_r[curr] - 1] ++;
		}
		else{
			dif = i - pos_r[curr - 1];
			if(dif % 2LL == 0LL)
				cnt[pos_r[curr - 1]] ++;
			else
				cnt[pos_r[curr - 1] - 1] ++;
		}

		if(i == pos_r[curr] - 1)
			curr ++;
	}

	for(ll i = 0;i < s.size();i ++)
		cout << cnt[i] << " ";
	cout << "\n";

	return 0;
}


Measured memory_bytes: 1864
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define pi acos(-1)
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

typedef vector<vector<lli> > matrix ;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{

    lli n;
    cin>>n;
    n --;
    lli ans = (n * (n + 1)) / 2;
    cout<<ans;
    cout<<"\n";
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
dp=[0]*31
for a,b in AB:
    x=1
    for i in range(30):
        if K&x and ((K-x)|(x-1))&a==a:
            dp[i]+=b
        x<<=1
    if K&a==a:
        dp[-1]+=b
print(max(dp))

Measured memory_bytes: 29428
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

string s;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	cout << ((s == "ABC") ? "ARC\n" : "ABC\n");
	return 0;
}

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

using namespace std;

int height,width;
std::vector<std::vector<pair<char,int>>> v;

// しろ -> .
// くろ -> #
// 探索した -> z

void tansaku(int n, int x, int y){
	v[x][y].first = 'z';
	if (v[x][y].second > n) {
		v[x][y].second = n;
	}
	int xx[] = {0,1,0,-1};
	int yy[] = {1,0,-1,0};
	for (size_t i = 0; i < 4; i++) {
		if (0 <= x+xx[i] && x+xx[i] < height && 0 <= y+yy[i] && y+yy[i] < width) {
			if (v[x+xx[i]][y+yy[i]].first == '.') {
				tansaku(n+1,x+xx[i],y+yy[i]);
			}
			if (v[x+xx[i]][y+yy[i]].first == 'z' && (v[x+xx[i]][y+yy[i]].second > n+1)) {
				tansaku(n+1,x+xx[i],y+yy[i]);
			}
		}
	}
}

int main(int argc, char const *argv[]) {
	std::cin >> height >> width;
	v.resize(height);
	int white = 0;
	for (size_t i = 0; i < height; i++) {
		string str;
		std::cin >> str;
		for (size_t j = 0; j < str.size(); j++) {
			v[i].push_back(make_pair(str[j],200));
			if (str[j] == '.') {
				white++;
			}
		}
	}

	tansaku(1, 0, 0);

	if (v[height-1][width-1].second == 200) {
		std::cout << -1 << '\n';
		return 0;
	}

	std::cout << white - v[height-1][width-1].second << '\n';



	return 0;
}


Measured memory_bytes: 512
#include<iostream> 
#include<string> 
#include<vector> 
#include<algorithm> 
using namespace std; 
int main()
{ 
	int n; 
	cin >> n; 
	vector<int> a(n); 
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a.at(i);
		sum += a.at(i);
	}
	sort(a.begin(), a.end());
	
	int q = 0;
	for (int i = 0; i < n; i++)
	{
		if (a.at(i)%2==1)
		{
			q = a.at(i); 
			break;
		}
	}
	if (sum % 2 == 0)
	{
		cout << sum / 2 << endl;
	}
	else
	{
		cout << (sum - q) / 2 << endl;
	}
	

}



Measured memory_bytes: 3160
N = int(input())
S =[]
for n in range(N):
    S.append(input())
T = []
M = int(input())
for m in range(M):
    T.append(input())
from collections import Counter
C_S = Counter(S)
C_T = Counter(T)
m = 0
for k,v in C_S.items():
    if v - C_T[k]>m:
        m =v - C_T[k]
print(m)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    int k;
    cin>>a>>b>>c>>k;
    for(int i = 1;i<=k;i++)
    {
        if(a >= b && a >= c)
        {
            a *= 2;
        }
        else if(b >= a && b >= c)
        {
            b *=  2;
        }
        else
        {
            c *= 2;
        }
    }
    cout<<a + b + c<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<double> vec;
typedef vector<vector<double>> mat;

int main(){
    int N;cin>>N;
    double x[10],y[10];
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
    }
    mat d(10,vec(10,0));
    double s=0;
    for(int i=0;i<N-1;i++){
        for(int j=i;j<N;j++){
            s+=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
        }
    }
    printf("%.10lf\n",(double)s*2/N);
    return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

const ll MOD = 1000000007;
int main() {
  int N, M; cin >> N >> M;
  vector<ll> a(M);
  vector<ll> box(N + 1);
  REP(i, M) {
    cin >> a[i];
    box[a[i]] = 1;
  }
  vector<ll> dp(N + 1, 1);
  for(int i = 0; i <= N; ++i) {
    if(box[i] == 1) {
      dp[i] = 0;
      if(box[i] == 1 && box[i - 1] == 1) {
        dp[N] = 0;
        break;
      }
      continue;
    } else {
      if(i >= 2) {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i] %= MOD;
      }
    }
  }
  cout << dp[N] << endl;
}

Measured memory_bytes: 5524
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
preorder & inorder

5
1 2 3 4 5
3 2 4 1 5

9
1 2 3 4 5 6 7 8 9
3 2 5 4 6 1 8 7 9

output:
postorder
3 4 2 5 1
"""

import sys


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


def reconstruction(_pre_order, _in_order):
    # write your code here
    if not _pre_order:
        return None
    root = TreeNode(_pre_order[0])
    root_position = _in_order.index(_pre_order[0])
    root.left = reconstruction(_pre_order=_pre_order[1:1 + root_position], _in_order=_in_order[:root_position])
    root.right = reconstruction(_pre_order=_pre_order[root_position + 1:], _in_order=_in_order[root_position + 1:])
    post_order.append(root.val)
    return root.val


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    pre_order = list(map(int, _input[1].split()))
    in_order = list(map(int, _input[2].split()))
    # assert len(pre_order) == len(in_order) == array_length

    post_order = []
    reconstruction(_pre_order=pre_order, _in_order=in_order)
    print(*post_order)

Measured memory_bytes: 7784
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

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

		int[][] ab = new int[m][2];
		for (int i = 0; i < m; i++) {
			ab[i][0] = sc.nextInt();
			ab[i][1] = sc.nextInt();
		}

		Arrays.sort(ab, Comparator.comparingInt(x -> x[1]));

		int last = -1;
		int ansewr = 0;
		for (int i = 0; i < m; i++) {
			if (last <= ab[i][0]) {
				last = ab[i][1];
				ansewr++;
			}
		}

		System.out.println(ansewr);
	}
}


Measured memory_bytes: 95092
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int a,p; cin>>a>>p;
    cout<<(a*3+p)/2<<endl;
}

Measured memory_bytes: 256