akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

vector<vector<int>> g;
vector<vector<int>> ec;
vector<vector<int>> vc;
vector<vector<int>> vd;
int n;

int f(int x, int l, int sum){
	sum++;
	rep(i, g.at(l).size()){
		vc.at(x).at(g.at(l).at(i)) = min(vc.at(x).at(l) + ec.at(l).at(i), vc.at(x).at(g.at(l).at(i)));
	}
	int mi = 2000000001;
	int k = 0;
	rep(i, n){
		if(vc.at(x).at(i) < mi && vd.at(x).at(i) == 0){
			mi = vc.at(x).at(i);
			k = i;
		}
	}
	vd.at(x).at(k) = 1;
	if(sum != n) f(x, k, sum);
	return 0;
}

int main(){
	int m, r;
	cin >> n >> m >> r;
	g = vector<vector<int>>(n, vector<int>(0));
	ec = vector<vector<int>>(n, vector<int>(0));
	vc = vector<vector<int>>(n, vector<int>(n));
	vd = vector<vector<int>>(n, vector<int>(n));
	vector<int> zi(r);
	rep(i, n) rep(j, n){
		vc.at(i).at(j) = 2000000000;
		vd.at(i).at(j) = 0;
	}
	rep(i, n){
		vc.at(i).at(i) = 0;
		vd.at(i).at(i) = 1;
	}
	rep(i, r){
		cin >> zi.at(i);
		zi.at(i)--;
	}
	rep(i, m){
		int a, b, cos;
		cin >> a >> b >> cos;
		a--; b--;
		g.at(a).push_back(b);
		g.at(b).push_back(a);
		ec.at(a).push_back(cos);
		ec.at(b).push_back(cos);
	}
	rep(i, n){
		f(i, i, 1);
	}
	sort(zi.begin(), zi.end());
	ll ans = 2000000000000000000;
	do{
		ll sum = 0;
		rep(i, r-1) sum += vc.at(zi.at(i)).at(zi.at(i+1));
		if(sum < ans) ans = sum;
	}while(next_permutation(zi.begin(), zi.end()));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<int>arr(n);
	vector<int>memo(2001);
	for(int i=0; i<n; i++){
		cin>>arr[i];
		memo[arr[i]]++;
	}
	for(int i=1; i<=2000; i++){
		memo[i]+=memo[i-1];
	}
	ll ans=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i==j)
			 continue;
			int upper=(arr[i]+arr[j]-1);
			int lower=abs(arr[i]-arr[j])+1;
			int temp=memo[upper]-memo[lower-1];
			if(arr[i]<=upper && arr[i]>=lower)
			 temp--;
			if(arr[j]<=upper && arr[j]>=lower)
			 temp--;
		//	cout<<" i , j , temp :  "<<arr[i]<<" "<<arr[j]<<" "<<temp<<"\n";
			ans+=temp;
		}
	}
	ans/=6;
	cout<<ans;
	return 0;
}

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

using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = __float80;

template<typename C>
i64 Size(const C &c) { return static_cast<i64>(c.size()); }

template<typename C>
void Sort(C &c) { std::sort(c.begin(), c.end()); }

template<typename C>
void SortR(C &c) { std::sort(c.rbegin(), c.rend()); }

template<typename T, typename U, typename Comp=std::less<>>
bool ChMax(T &x_max, const U &x, Comp comp={}) {
  if(comp(x_max, x)) {
    x_max = x;
    return true;
  }
  return false;
}

template<typename T, typename U, typename Comp=std::less<>>
bool ChMin(T &x_min, const U &x, Comp comp={}) {
  if(comp(x, x_min)) {
    x_min = x;
    return true;
  }
  return false;
}

struct ProconInit {
  static constexpr int IOS_PREC = 15;
  static constexpr bool AUTOFLUSH = false;

  ProconInit() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(IOS_PREC);
    if (AUTOFLUSH) std::cout << std::unitbuf;
  }
} PROCON_INIT;

void solve() {
  i64 x; std::cin >> x;
  i64 y; std::cin >> y;
  i64 z; std::cin >> z;

  i64 tmp = 0;

  tmp = x;
  x = y;
  y = tmp;

  tmp = x;
  x = z;
  z = tmp;

  std::cout << x << " " << y << " " << z << "\n";
}

signed main() {
  solve();

  return 0;
}


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

int main() {

    int N,M;
    cin >> N >> M;
    
    int sum = 0;
    int x;
    
    rep (i,M) {
        cin >> x;
        sum += x;
    }
    
    if (N - sum >= 0) {
        cout << N - sum << endl;
    }
    
    else { cout << -1 << endl;
         }
    
}


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

int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    ll dp[n][k+1];
    for(int j=0;j<n;j++)
        dp[j][0]=1;
   // cout<<"EE"<<endl;
    for(int i=0;i<k+1;i++)
    {
        if(i<=a[0])
            dp[0][i]=1;
        else
            dp[0][i]=0;
    }
   // cout<<"EE"<<endl;
    for(int i=1;i<k+1;i++)
    {
       // dp[0][i]=dp[0][i-1]+dp[0][i];
       // dp[0][i]%=M;
    }
//cout<<"EE"<<endl;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<k+1;j++)
        {
            
                int low=max(j-a[i],0);
                int high=j;
                int sum=0;
               
                //cout<<low<<" "<<high<<endl;
                if(low==0)
                {
                    dp[i][j]=dp[i-1][high];
                    dp[i][j]%=M;
                }
                else 
                {
                    dp[i][j]=dp[i-1][high]-dp[i-1][low-1];
                    if(dp[i][j]<0)
                        dp[i][j]+=M;
                    dp[i][j]%=M;
                }
            
           
        }
        for(int j=1;j<k+1;j++)
        {
            dp[i][j]=dp[i][j-1]+dp[i][j];
            //cout<<dp[i][j]<<" "<<"ES"<<endl;
            dp[i][j]%=M;
        }
    }


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

Measured memory_bytes: 78336
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


typedef long long LL;

double calc( int n, double value, int k, double p ) {
    return value * (int)( n / k * k ) * p + ( n % k ) * value;
}

LL solve( int n ) {
    LL res = INT_MAX;
    int W[3] = { 200, 300, 500 };
    int V[3] = { 380, 550, 850 };
    int K[3] = { 5, 4, 3 };
    double P[3] = { 0.8, 0.85, 0.88 };
    for ( int a = 0; a < 100; ++ a ) {
        for ( int b = 0; b < 100; ++ b ) {
            for ( int c = 0; c < 100; ++ c ) {
                int sumW = W[0] * a + W[1] * b + W[2] * c;
                if ( sumW != n ) continue;
                res = min( res,
                           (LL)(calc( a, V[0], K[0], P[0] )
                           + calc( b, V[1], K[1], P[1] )
                            + calc( c, V[2], K[2], P[2] )));
            }
        }
    }
    return res;
}

int main() {
    int n;
    while ( cin >> n && n ) {
        cout << solve( n ) << endl;
    }
    return 0;
}

Measured memory_bytes: 864
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(min(a + b, b + c), a + c) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>

struct TestData
{
  int testNum;
  std::string input;
  std::string expectedOutput;
};

struct TestResult
{
  std::string testOutput;
  bool testPassed;
};

void testSolution();
TestResult runTestCase(const TestData& testData);
std::string formatResult(const TestData& testData, const TestResult& testResult);
void solution(std::istream& is, std::ostream& os);

static const bool IS_TESTING = false;

// define test data
static const std::vector<TestData> testDatas = {
  {1, "2 4\n", "8\n"},
  {2, "2 -4\n", "6\n"},
  {3, "-2 4\n", "2\n"},
  {4, "-2 -4\n", "8\n"},
};

int main()
{
  if (IS_TESTING)
    testSolution();
  else
    solution(std::cin, std::cout);

  return 0;
}

void testSolution()
{
  for (const auto& testData : testDatas) {
    auto testResult = runTestCase(testData);

    std::cout << formatResult(testData, testResult);
  }
}

TestResult runTestCase(const TestData& testData)
{
    std::istringstream iss {testData.input};
    std::ostringstream oss {};

    solution(iss, oss);

    auto testOutput = oss.str();
    auto testPassed = testData.expectedOutput.compare(testOutput) == 0;
    
    return {testOutput, testPassed};
}

std::string formatResult(const TestData& testData, const TestResult& testResult)
{
  std::ostringstream oss {};

  oss << "Test " << std::setw(2) << testData.testNum << ": "
    << (testResult.testPassed ? "Passed!" : "Failed!") << std::endl;
  
  oss << "\tExpected: " << testData.expectedOutput << "\tActual: " << testResult.testOutput << std::endl;

  return oss.str();
}

// solution to the problem
void solution(std::istream& is, std::ostream& os)
{
  int num1, num2; is >> num1 >> num2;

  int sum = num1 + num2;
  int prod = num1 * num2;
  int diff = num1 - num2;

  os << std::max({sum, prod, diff}) << std::endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int N;
int A[200000];
int cnt[1000000+1];
int chk[1000000+1];
int main(){
  int i;
  int res = 0;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(N);i++){
    cnt[A[i]]++;
  }
  for(i=(0);i<(1000000+1);i++){
    if(cnt[i]){
      int j;
      for(j=(i);j<(1000000+1);j+=(i)){
        chk[j] += cnt[i];
      }
    }
  }
  for(i=(0);i<(N);i++){
    if(chk[A[i]]==1){
      res++;
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// int N, A[2d5];
// int cnt[1d6+1];
// int chk[1d6+1];
// {
//   int res = 0;
//   rd(N,A(N));
//   rep(i,N) cnt[A[i]]++;
//   rep(i,1d6+1) if(cnt[i]){
//     rep(j,i,1d6+1,i) chk[j] += cnt[i];
//   }
//   rep(i,N) if(chk[A[i]]==1) res++;
//   wt(res);
// }


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int main() {

  int c[3][3];
  rep(i, 3) rep(j, 3) {
    cin >> c[i][j];
  }

  int a[3];
  REP(x, -100, 101) REP(y, -100, 101) REP(z, -100, 101) {
    int a[] = {x, y, z};
    int b[] = {c[0][0] - a[0], c[1][1] - a[1], c[2][2] - a[2]};
    rep(i, 3) rep(j, 3) {
      if (c[i][j] != a[i] + b[j]) {
        goto next;
      }
    }
    cout << "Yes\n";
    exit(0);
    next:;
  }
  cout << "No\n";
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


vector<int> v[303030];
int main(){
    int n,m;
    cin>>n>>m;
    rep(i,m){
        int x,y;
        cin>>x>>y;
        --x;--y;
        v[x].push_back(y+n);
        v[x+n].push_back(y+2*n);
        v[x+2*n].push_back(y);
    }
    int s,t;
    cin>>s>>t;
    --s;--t;
    vector<int> dist(3*n,inf);
    dist[s]=0;
    queue<int> q;
    q.push(s);
    while(q.size()){
        int cur=q.front();q.pop();
        for(auto to : v[cur]){
            if(dist[to]>dist[cur]+1){
                dist[to]=dist[cur]+1;
                q.push(to);
            }
        }
    }
    if(dist[t]==inf)cout<<-1<<endl;
    else cout<<dist[t]/3<<endl;
    return 0;
}

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

Measured memory_bytes: 128
import heapq

n=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)

hp=[]

ans=0
heapq.heappush(hp,-A[0])

for a in A[1:]:
    ans+=heapq.heappop(hp)
    heapq.heappush(hp,-a)
    heapq.heappush(hp,-a)
print(-ans)

Measured memory_bytes: 31628
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

ll A[200010];

int main() {
	ll N, K;
	cin >> N >> K;
	for(int i=0; i<N; ++i) cin >> A[i];
	sort(A, A+N);
	ll neg=-1, pos=N;
	for(int i=0; i<N; ++i){
		if(A[i]>=0 && neg<0) neg=i;
		if(A[i]>0 && pos==N) pos=i;
	}
	if(K<=neg*(N-pos)){
		ll le=-2e18, ri=0;
		while(le+1<ri){
			ll mid=le+(ri-le)/2;
			int now=pos;
			ll sum=0;
			for(int i=0; i<neg; ++i){
				while(now<N){
					if(A[i]*A[now]<=mid) break;
					++now;
				}
				sum += N-now;
			}
			if(sum>=K) ri=mid;
			else le=mid;
		}
		cout << ri << endl;
		return 0;
	}else{
		K -= neg*(N-pos);
	}
	ll zer=pos-neg;
	if(K<=zer*(zer-1)/2+zer*(N-zer)){
		cout << 0 << endl;
		return 0;
	}else{
		K -= zer*(zer-1)/2+zer*(N-zer);
		ll le=0, ri=2e18;
		while(le+1<ri){
			ll mid=le+(ri-le)/2, sum=0;
			int now=N-1;
			for(int i=pos; i<N; ++i){
				while(now>=pos){
					if(A[i]*A[now]<=mid) break;
					--now;
				}
				sum += max(now-i, 0);
			}
			now=0;
			for(int i=neg-1; i>=0; --i){
				while(now<neg){
					if(A[i]*A[now]<=mid) break;
					++now;
				}
				sum += max(i-now, 0);
			}
			if(sum>=K) ri=mid;
			else le=mid;
		}
		cout << ri << endl;
	}
	return 0;
}

Measured memory_bytes: 1792
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif




#define int long long
#define rng(i,l,r) for(size_t i=(l);i<(r);++i)
#define rep(i,n) rng(i,0,n)
#define gnr(i,l,r) for(size_t i=(r)-1;i>=(l);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(obj) (obj).begin(), (obj).end()   //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend()//...,3,2,1

using namespace std;
//using ll = long long;


const int MOD = 1000000007;
const int INF = 1e18;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

const double pi = acos(-1);



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; }


using Graph = vector<vector<int>>;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
//*max_element(ALL(vector))
//count(ALL(vector),num) -> n




void solve(){
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s; cin >> s;
    int znum = 0;
    int onum = 0;
    rep(i,s.size()){
        if(s[i]=='1') onum++;
        if(s[i]=='0') znum++;
    }
    
    cout << min(onum,znum)*2 << endl;
    
    
    
    
    
    
    
}



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



Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main() {
	int A = 0;

	for (int i = 0; i < 4; i++) {
		int N;
		cin >> N;

		A += N;
	}

	int m = A / 60;
	int s = A % 60;

	cout << m << endl;
	cout << s << endl;

	return 0;
}


Measured memory_bytes: 3116
#include <stdio.h>

int main(){

  int N,i,v,j,k,A[1000];

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(k=0;k<N-1;k++){
    printf("%d ",A[k]);
  }
  printf("%d\n",A[N-1]);
    
  for(i=1;i<=N-1;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    for(k=0;k<N-1;k++){
      printf("%d ",A[k]);
    }
    printf("%d\n",A[N-1]);
  }
  return 0;
}

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

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

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  char s;
  cin>>s;
  map<char,char>m;
  m['A']='T';
  m['T']='A';
  m['C']='G';
  m['G']='C';
  cout<<m[s]<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    string S;
    cin >> N;
    cin >> S;
    if(N%2 == 1) cout << "No" << endl;
    else{
        bool flg = true;
        for(int i=0;i<N/2;i++){
            if(S[i] != S[N/2 + i]){
                flg = false;
                break;
            }
        }
        if(flg == true) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	int ac = 0, wa = 0, tle = 0, re = 0;
	while(n--){
		string str; cin>>str;
		if(str == "AC") ac++;
		else if(str == "WA") wa++;
		else if(str == "TLE") tle++;
		else if(str == "RE") re++;
	}
	cout<<"AC x "<<ac<<'\n';
	cout<<"WA x "<<wa<<'\n';
	cout<<"TLE x "<<tle<<'\n';
	cout<<"RE x "<<re<<'\n';
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll


signed main() {
  rep(i, 5) {
    int x; cin >> x;
    if(x == 0) {
      cout << i+1 << endl;
      return 0;
    }
  }

}

Measured memory_bytes: 3636
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptor/reversed.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
namespace lib
{
	template<class T>constexpr T pow(T val, std::uint64_t p)
	{
		auto ret = T(1);
		for (auto i : boost::irange(0, 63))
		{
			if (p & (1ULL << i))
			{
				ret *= val;
			}
			val *= val;
		}
		return ret;
	}
	template<std::uint64_t Mod>class modnum :
		private boost::addable<modnum<Mod>>,
		private boost::subtractable<modnum<Mod>>,
		private boost::multipliable<modnum<Mod>>,
		private boost::dividable<modnum<Mod>>
	{
		std::uint64_t val;
		void clamp()
		{
			val %= Mod;
		}
	public:
		modnum() = default;
		modnum(std::int64_t v) :val()
		{
			if (v < 0)
			{
				v += (std::abs(v) / Mod + 1) * Mod;
			}
			val = v;
			clamp();
		}
		modnum(std::uint64_t v) :val(v)
		{
			clamp();
		}
		modnum(std::int32_t v) :modnum(static_cast<std::int64_t>(v))
		{

		}
		modnum(std::uint32_t v) :modnum(static_cast<std::uint64_t>(v))
		{

		}
		friend std::ostream& operator<<(std::ostream& os, modnum const& num)
		{
			return os << num.val;
		}
		auto& operator+=(modnum const& rhs)
		{
			val += rhs.val;
			clamp();
			return *this;
		}
		auto& operator-=(modnum const& rhs)
		{
			val += Mod - rhs.val;
			clamp();
			return *this;
		}
		auto& operator*=(modnum const& rhs)
		{
			val *= rhs.val;
			clamp();
			return *this;
		}
		auto& operator/=(modnum const& rhs)
		{
			val *= pow(rhs, Mod - 2).val;
			clamp();
			return *this;
		}
		auto const& operator*()const
		{
			return val;
		}
	};
}
using mod_t = lib::modnum<1000000007>;


void Main()
{
	int H, W;
	std::cin >> H >> W;
	boost::multi_array<bool, 2> data(boost::extents[H][W]);
	for (int i : boost::irange(0, H))
	{
		for (int j : boost::irange(0, W))
		{
			char c;
			std::cin >> c;
			if (c == '#')
			{
				data[i][j] = true;
			}
		}
	}
	boost::multi_array<int, 2> count(boost::extents[H][W]);
	for (int i : boost::irange(0, H))
	{
		for (int j = 0; j < W; ++j)
		{
			auto s = j;
			while (j < W && !data[i][j])
			{
				++j;
			}
			for (int k : boost::irange(s, j))
			{
				count[i][k] += j - s;
			}
		}
	}
	for (int j : boost::irange(0, W))
	{
		for (int i = 0; i < H; ++i)
		{
			auto s = i;
			while (i < H && !data[i][j])
			{
				++i;
			}
			for (int k : boost::irange(s, i))
			{
				count[k][j] += i - s;
			}
		}
	}
	int max = 0;
	for (auto&& ar : count)
	{
		for (auto&& v : ar)
		{
			max = std::max(max, v - 1);
		}
	}
	std::cout << max << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 19840
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
LL S;
int main(){
	cin>>S;
	printf("0 0 ");
	if (S%1000000000==0){
		printf("%lld %lld %lld %lld\n",1000000000ll,0ll,1ll,S/1000000000);
	}
	else printf("%lld %lld %lld %lld\n",1000000000ll,1000000000ll-S%1000000000,1ll,S/1000000000+1);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int a, b;
int total;

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

	if (a == b)cout << a * 2;

	else
	{
		if (a > b) {
			total = 2 * a - 1;
			cout << total;
		}
		else
		{
			total = 2 * b - 1;
			cout << total;
		}
	}
	return 0;
	
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MN 105
using namespace std;
int n,m,ex,ey,ans,sum[MN][MN],f[MN][MN][MN];
char ch[MN];
int C(int a,int b,int c,int d){return sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",ch+1);
		for(int j=1;j<=m;j++)if(ch[j]=='o')sum[i][j]++;else if(ch[j]=='E')ex=i,ey=j;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	int up,down,left,right;memset(f,-0x3f,sizeof(f));f[0][0][0]=0;
	for(int u=0;u<=n;u++){
		if(ex-u<1)break;
		for(int d=0;d<=n;d++){
			if(ex+d>n)break;
			up=max(ex-u,1+d);
			down=min(ex+d,n-u);
			if(up>down)continue;
			for(int l=0;l<=m;l++){
				if(ey-l<1)break;
				for(int r=0;r<=m;r++){
					if(ey+r>m)break;
					left=max(ey-l,r+1);
					right=min(ey+r,m-l);
					if(left>right)continue;
					ans=max(ans,f[d][l][r]);
					if(ex+d<n-u)f[d+1][l][r]=max(f[d+1][l][r],f[d][l][r]+C(ex+d+1,left,ex+d+1,right));
					if(ey-l>r+1)f[d][l+1][r]=max(f[d][l+1][r],f[d][l][r]+C(up,ey-l-1,down,ey-l-1));
					if(ey+r<m-l)f[d][l][r+1]=max(f[d][l][r+1],f[d][l][r]+C(up,ey+r+1,down,ey+r+1));
					if(ex-u>d+1)f[d][l][r]=f[d][l][r]+C(ex-u-1,left,ex-u-1,right);
				}
			}
		}
	}printf("%d\n",ans);	
}



Measured memory_bytes: 4736
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        sc.close();

        // 主処理
        int result = n.length() - n.replaceAll("2", "").length();

        // 出力
        System.out.println(result);
    }
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 18) + 1;
	
	char buf[L], *S , *T, c;
	 
	char getchar() {
		if(S == T) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}
	
	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	char B[25], *outs=B+20, *outr=B+20;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;
		
		if(!a)*--outs = '0';
		else 
			while(a)
				*--outs = (a % 10) + 48, a /= 10;
		
		if(x)
			*--outs = x;
		
		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inp_ll;

const int MAXN = 200010;

int n;
int a[MAXN], p[MAXN], u[MAXN];

int main()
{
	
	n = inp();
	for (int i = 1; i <= n; ++ i)
	{
		a[i] = inp();
		p[a[i]] = i;
	}
	int ans = n-1;
	for (int i = 1; i <= n; ++ i)
	{
		if (u[i]) continue;
		for (int j = i+1; j <= n+1; ++ j)
		{
			if (p[j-1] > p[j])
			{
				ans = min(ans, n-(j-i));
				break;
			}
			u[j] = 1;
		}
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 2816
#include <stdio.h>
#define LL long long
#define eps 1e-6
int main(){
	LL a,b,c;
	double d;
	scanf("%lld%lf",&a,&d);
	d+=eps;
	b=d*100;
	c=a*b/100;
	printf("%lld\n",c);
}


Measured memory_bytes: 1680
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <cmath>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define step(i, f, n, a) for(int (i) = (f); (i) < (n); (i)+=a)
#define rstep(i, f, n, a) for(int (i) = (f); (i) >= (n); (i)-=a)
#define p(...) printf(__VA_ARGS__); cout << endl;
#define gets(x) x; cin >> x;
#define puts(x) x; cout << x << endl;
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](const a, const b){ return c ;}
#define key(t, x, compare) [](const t& a, const t& b){ return a x compare b x ;}

using namespace std;

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

int main(){
	int n;
	gets(n)
	puts( (n*800) - ((n/15)*200) )
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include "math.h"
#include "assert.h"

using namespace std;

int inf = std::numeric_limits<int>().max();

#define BUFF ios::sync_with_stdio(false)
#define epsilon 1e-07
#define pi 2 * acos(0.0);
#define mod 1000000007   // 1e9+7
#define ll long long
#define cerr if(false)cerr
#define watch(x) cerr << #x << " = " << x << endl;

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

	multiset<int> s;

	ll t = 1;
	s.insert(- v[0]);
	for(int i=1; i<n; i++) {
		auto it = s.upper_bound(-v[i]);	
		if (it != s.end()) {
			auto it1 = it;
			it1++;
			s.erase(it, it1);
		} else t++;
		s.insert( - v[i]);
	}
	cout << t << endl;
}


Measured memory_bytes: 5376
// All Pairs Shortest Path
// 所要時間 分
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()

int main() {

    int v, e;
    cin >> v >> e;
    const long long INF = 10000000000000000;
    vector<vector<long long> > cost(v, vector<long long>(v, INF));
    rep(i, e){
        int s, t, d;
        cin >> s >> t >> d;
        cost[s][t] = d;
    }
    rep(i, v){
        cost[i][i] = 0;
    }

    rep(k, v){
        rep(i, v){
            rep(j, v){
                if(cost[i][k] != INF && cost[k][j] != INF){
                    cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
                }
            }
        }
    }
    bool nega = false;
    rep(i, v){
        if(cost[i][i] < 0){
            nega = true;
        }
    }

    if(nega){
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    rep(i, v){
        rep(j, v){
            if(cost[i][j] == INF){
                cout << "INF";
            }
            else{
                cout << cost[i][j];
            }
            if(j != v-1){
                cout << " ";
            }
        }
        cout << endl;
    }

    return 0;
}


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

using namespace std;


const long inf=1000000000;
long n,m,l;
 long r[9];
bool used[9]={false};
long res;
long dist[205][205];

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


void dfs(long c,long v,long dis){
  if(c==l) {
    res=min(res,dis);
    return;
  }
  
  rep(i,l){
   if(!used[i]){
    used[i]=true;
     if(v==-1) dfs(c+1,i,0);
     else dfs(c+1,i,dis+dist[r[v]][r[i]]);
     used[i]=false;
   }
  
  }
    
}

int main(){
  cin >> n >> m >> l;
  rep(i,l) {
    cin >> r[i];
    r[i]--;
  }
  
  
  rep(i,n){
   rep(j,n) {
     if(i!=j) dist[i][j]=inf;
     else dist[i][j]=0;
   }
   }
    
  rep(i,m){
   long a,b,c;
    cin >> a >> b >> c;
    a--;
    b--;
    dist[a][b]=c;
    dist[b][a]=c;
  } 
  
  rep(k,n){
    rep(i,n){
      rep(j,n) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
      }
  }
 
  res=inf;
  dfs(0,-1,0);
  cout << res << endl;
  

}

Measured memory_bytes: 512
/* **********************************JAI SAI RAM ************************************* */
//HELP IN CODEFORCES ROUND 641
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);   
    vector<ll> v(5);
    cin>>v[0]>>v[1]>>v[2]>>v[3]>>v[4];
    ll i;
    for(i=1;i<=5;i++)
    {
        if(v[i-1]==0)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){

  int N,K;
  cin >> N >> K;

  int ans = 1;

  for(int i = 0;i < N;i++){
    if(ans + K < 2 * ans)ans += K;
    else ans*=2;
  }

  cout << ans << endl;



  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N;
  cin >> N;
  vector<int> W(N);
  rep(i, N) cin >> W[i];
  int total = 0;
  rep(i, N) total += W[i];
  int cur = 0;
  int ans = 1e6;
  for (int i = 0; i < N; i++) {
    cur += W[i];
    ans = min(ans, abs(total - 2 * cur));
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3604
h, w, n = map(int, input().split())
sr, sc = map(int, input().split())
S = input()[::-1]
T = input()[::-1]

r_bound = w
l_bound = 1
d_bound = h
u_bound = 1

remain = True

for s, t in zip(S, T):
    if t =='R' and l_bound > 1:
        l_bound -= 1
    elif t =='L' and r_bound < w:
        r_bound += 1
    elif t =='D' and u_bound > 1:
        u_bound -= 1
    elif t =='U' and d_bound < h:
        d_bound += 1
    if s =='R':
        r_bound -= 1
    elif s =='L':
        l_bound += 1
    elif s =='D':
        d_bound -= 1
    elif s =='U':
        u_bound += 1
    if (r_bound < l_bound) or (d_bound < u_bound):
        remain = False
        break
if (sc < l_bound or sc > r_bound) or (sr < u_bound or sr > d_bound):
    remain = False

if remain:
    print('YES')
else:
    print('NO')

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)
#define mod 1000000007
typedef long long ll;

int main() {
    int n,sum=0,sum2=0,min=mod;cin>>n;

    vector<int>w(n);
    rep(i,n){
        cin>>w[i];
        sum+=w[i];
    }

    rep(i,n-1){
        sum2+=w[i];
        if(abs(sum2-(sum-sum2))<min){
            min=abs(sum2-(sum-sum2));
        }
    }
    cout<<min<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
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 main(){
    ll a, b, c;
    cin >> a >> b >> c;
    if (a <= c && c <= b) cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <random>
#include <string>

int main() {
  std::string S;
  std::cin >> S;
  int K = 1;

  std::string before_s = S.substr(0, 1);
  S.erase(S.begin());

  while (S.size() > 0) {
    if (S.substr(0, 1) == before_s) {
      if (S.size() == 1) {
        break;
      } else {
        before_s = S.substr(0, 2);
        S.erase(S.begin(), S.begin() + 2);
        K++;
        continue;
      }
    } else {
      before_s = S.substr(0, 1);
      S.erase(S.begin());
      K++;
      continue;
    }
  }

  std::cout << K;
}

Measured memory_bytes: 640
#include<cstdio>
//1 can't be throw
long long sum0[200005];
//1 can be throw
long long sum1[200005];
//2 can't be throw
long long sum2[200005];
//2 can be throw
long long sum3[200005];
//2, 1, ready for ans
long long sum4[200005];
long long sum[200005];
long long a[200005];
long long b[200005];

long long min(long long a,long long b){ return a>b?b:a; }

void preWork(int n){
    sum[0] = 0;
    long long allSum = 0;
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i-1]+a[i];
        allSum += a[i];
        sum0[i] = sum0[i-1]+(a[i]%2!=1);
        sum2[i] = sum2[i-1];
        int cost = 0;
        if(a[i]==0) cost = 2;
        else cost = a[i]%2;
        sum2[i] += cost;
        sum1[i] = min(allSum,sum1[i-1]+(a[i]%2!=1));
        sum3[i] = min(allSum,sum3[i-1]+cost);
    }
}
//even, odd, even
//but not even/odd
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%lld",&a[i]);
        b[n-i+1] = a[i];
    }
    long long ans = n;
    preWork(n);
    long long minn = 0;
    ans = min(ans,sum[n]);
    for(int i = 1; i <= n; i++){
        minn = min(minn,sum3[i]-sum0[i]);
        sum4[i] = min(sum0[i]+minn,sum1[i]);
    }
    //for(int i = 1; i <= n; i++) printf("sum3[%d] = %lld\n",i,sum3[i]);
    //printf("\n");
    minn = 0;
    for(int i = 1; i <= n; i++){
        minn = min(minn,sum4[i]-sum2[i]);
        long long cur = min(sum3[i],sum2[i]+minn)+sum[n]-sum[i];
        ans = min(ans,cur);
    }
    printf("%lld\n",ans);
    return 0;
}


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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

int N, M;
int dp[3300][3300][2];
int mod = 1e9 + 7;
signed main() {
    cin >> N >> M;
    dp[0][0][1] = 1;
    for (int i = 1; i <= N; i++)dp[0][i][0] = 1;
    for (int i = 0; i < M; i++) {
        (dp[i + 1][0][1] += dp[i][0][1]) %= mod;
        (dp[i + 1][1][1] += dp[i][0][1]) %= mod;

        (dp[i + 1][1][1] += dp[i][1][0]) %= mod;
        (dp[i + 1][0][1] += dp[i][1][0]) %= mod;
        (dp[i + 1][1][1] += dp[i][1][1]) %= mod;
        (dp[i + 1][0][1] += dp[i][1][1]) %= mod;
        if (N != 1) {
            (dp[i + 1][1][0] += dp[i][1][0]) %= mod;
            (dp[i + 1][2][0] += dp[i][1][0]) %= mod;
            (dp[i + 1][1][1] += dp[i][1][1]) %= mod;
            (dp[i + 1][2][1] += dp[i][1][1]) %= mod;
        }
        for (int j = 2; j < N; j++) {
            (dp[i + 1][j][0] += 2 * dp[i][j][0]) %= mod;
            (dp[i + 1][j - 1][0] += dp[i][j][0]) %= mod;
            (dp[i + 1][j + 1][0] += dp[i][j][0]) %= mod;
            (dp[i + 1][j][1] += 2 * dp[i][j][1]) %= mod;
            (dp[i + 1][j - 1][1] += dp[i][j][1]) %= mod;
            (dp[i + 1][j + 1][1] += dp[i][j][1]) %= mod;
        }
        if (N != 1) {
            (dp[i + 1][N][0] += dp[i][N][0]) %= mod;
            (dp[i + 1][N - 1][0] += dp[i][N][0]) %= mod;
            (dp[i + 1][N][1] += dp[i][N][1]) %= mod;
            (dp[i + 1][N - 1][1] += dp[i][N][1]) %= mod;
        }
    }
    int ans = 0;
    for (int i = 0; i <= N; i++)(ans += dp[M][i][1]) %= mod;
    cout << ans << endl;

}


Measured memory_bytes: 155904
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
sA = sum(A)
cA = Counter(A)
for i in range(q):
    b,c = map(int, input().split())
    diff = 0
    if cA.get(b):
        diff = (c-b) *cA[b]
    sA += diff
    print(sA)
    cA[c] += cA[b]
    cA[b] = 0


Measured memory_bytes: 24112
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

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;}

const ll MOD = 1000000007;
const int INF = 1<<29;
//const ll INF = (ll)1e18 + 1;


int main(){
  ll A, B, N; cin >> A >> B >> N;
  ll X;
  if (N >= B) X = B - 1;
  else X = N;
  ll ans = floor(A * X / B) - A * floor(X / B);
  cout << ans << endl;
}


Measured memory_bytes: 3600
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=read::<String>().chars().collect::<Vec<char>>();
    let mut f=false;
    for i in 0..a.len(){
        for j in i+1..a.len(){
            if a[i as usize]==a[j as usize]{f=true}
        }
    }
    println!("{}",if f{"no"}else{"yes"})
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

vector<int> ans[400];
int n;
int k,l;
int to = 1;
void answer(int len, int from ){
    if(len == 0 ) return;
    Rep(i,len){
        ans[len-1].push_back(to);
        if(i == len-1 ) break;
        to++;
    }

    Rep(i,len){
        ans[i].push_back(from);
        if(i == len-1 ) break;
        from++;
    }

    answer(len-1,from);
    return;
}

int main() {

    Scd(n);

    int ok = false;
    for(int i = 1; i < 1000; i++){
        if( i * (i+1) == n*2 ){
            ok = true;
            k = i+1;
            l = i;
            break;
        }
    }

    YesNo(ok);
    if(!ok) return 0;

    answer(k,1);

    printf ("%d\n", k);
    Rep(i,k){
        printf ("%d ", l);
        Rep(j,l){
            printf ("%d", ans[i][j]);
            if( j != l-1 ) printf (" ");
        }
        printf ("\n");
    }

    return 0;
}



Measured memory_bytes: 2304
def main():
    dist = []
    import numpy as np
    from collections import deque
    n, x, y = map(int,input().split())
    g = [[] for _ in range(n)] 
    for i in range(n-1):

        g[i] += i+1,
        g[i+1] += i,
    g[x-1] += y-1,
    g[y-1] += x-1,
    a = [0]*n
    for start in range(n):
        d = [-1] * n
        d[start] = 0
        q = deque([start])
        add,pop=q.append,q.popleft
        while q:
            v = pop()
            for nv in g[v]:
                if d[nv] < 0:
                    d[nv] = d[v]+1
                    add(nv)
        for i in d:
            a[i] += 1
    #     dist.append(d)
    # dist = np.array(dist).flatten()
    # for i in range(1,n):
    #     print(int(np.count_nonzero(dist==i)/2))
    for i in range(1,n):
        print(int(a[i]/2))
    # print(' '.join(str(i//2) for i in a[1:]))
main()

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

using namespace std;
typedef unsigned long long llint;

llint a, b;
bool prost(llint x) {
    //bool flag = true;
    for (llint a = 2; a * a <= x; a++)
        if (x % a == 0) return false;
    return true;
}

llint gcd(llint a, llint b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    cin >> a >> b;
    llint gc = gcd(a, b);

    llint sol = 0;
    for (llint i = 1; i * i <= gc; i++) {
        if (gc % i == 0) {
            llint tren = gc / i;
            sol += prost(i) + (tren != i) * prost(tren);
        }
    }
    printf("%lld\n", sol);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator > (long&& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};

struct Solver {
  std::string s[2];
  Solver() {
    S002 reader;
    reader >= s[0] >= s[1];
  }
  void solve() {
    long n = s[0].size() + s[1].size();
    for(long i = 0; i < n; ++i) {
      putchar(s[i%2][i/2]);
    }
    putchar('\n');
  }    
  ~Solver() { fprintf(stderr, "--end--\n"); }
};
 

int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<complex>
#include<cmath>
#include <cstdio>

using namespace std;

typedef complex<double> xy_t;
xy_t P[110];

// 図(1) 内積: a.x*b.x +a.y*b.y (jajjbj cos  に一致)
double dot_product(xy_t a, xy_t b) { return (conj(a)*b).real(); }
// 図(2) クロス(外) 積: a.x*b.y - b.x*a.y
// ベクトルa,b が作る三角形の符号付き面積の二倍
double cross_product(xy_t a, xy_t b) { return (conj(a)*b).imag(); }
// (図なし) 射影: 原点とp を結ぶ直線にb を射影
xy_t projection(xy_t p, xy_t b) { return b*dot_product(p,b)/norm(b); }

int main(){
	int N = 0;
	double x, y;
	while (scanf("%lf,%lf", &x, &y) != EOF){
		P[N++] = xy_t(x,y);
		//cout << x <<" "<< y << endl;
	}

	//for(int i = 0; i < 22; ++i){
	//	cin >> x >> y;
	//	P[N++] = xy_t(x,y);
	//}
	//面積計算
	double S = 0.0;
	for (int i=0; i+2<N; ++i){
		xy_t a=P[0], b=P[i+1], c=P[i+2];
		S += cross_product(b - a, c - a) / 2.0000000;
	}
	printf("%.6f\n", abs(S));
}


Measured memory_bytes: 3204
import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)
C = - np.array(input().split(), dtype=np.int64)

A.sort()
#B.sort()
C.sort()

cnt_A = np.searchsorted(A,B,side='left')
cnt_C = np.searchsorted(C,-B,side='left')

answer = (cnt_A * cnt_C).sum()
print(answer)


Measured memory_bytes: 27696
a, b, c, x, y = tuple(map(lambda i: int(i), input().split()))

# 個別買い
p1 = a * x + b * y

# セット＋残りを個別
p2 = c * min(x, y) * 2 + (a * (x - y) if x > y else b * (y - x))

# セットのみ
p3 = c*max(x, y)*2

print(min(p1, p2, p3))

Measured memory_bytes: 3060