akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define mk make_pair
#define f first
#define s second
using namespace std;
int n,m,p1,p2,dp[201][1001][1001];
map<pair<int,pair<int,int> >,int >m1;

vector<pair<int,int> >v;

int dfs(int d,int h,int w){
  int res=0;
  if(m1[mk(d,mk(h,w))])return m1[mk(d,mk(h,w))];
  if(d==v.size()) return 1;
  if(v[d].f<h&&v[d].s<w)
    res=max(res,dfs(d+1,v[d].f,v[d].s))+1;
  res=max(res,dfs(d+1,h,w));
  return m1[mk(d,mk(h,w))]=res;
}

main(){
  while(cin>>n,n){
    m1.clear();
    v.clear();
    for(int i=0;i<n;i++){
      cin>>p1>>p2;
      v.push_back(mk(p2,p1));
    }
    cin>>m;
    for(int i=0;i<m;i++){
      cin>>p1>>p2;
      v.push_back(mk(p2,p1));
    }
    stable_sort(v.begin(),v.end(),greater<pair<int,int> >());
    for(int i=0;i<v.size();i++)swap(v[i].f,v[i].s);
    stable_sort(v.begin(),v.end(),greater<pair<int,int> >());
    cout<<dfs(0,1001,1001)-1<<endl;
  }
}

Measured memory_bytes: 3800
// Best dish by Chef at the Michelin's, Vatican
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

const int maxN = 200000 + 5;
int n, k, a[maxN];
set<int> S;

int C[maxN];
void add(int p, int x) {
	for(; p <= n; p += p & -p) C[p] += x;
}
int sum(int p) {
	int r = 0;
	for(; p > 0; p -= p & -p) r += C[p];
	return r;
}

int f[20][maxN], g[20][maxN], lg[maxN];

int qmax(int x, int y) {
	int k = lg[y - x + 1];
	return max(f[k][x], f[k][y - (1 << k) + 1]);
}
int qmin(int x, int y) {
	int k = lg[y - x + 1];
	return min(g[k][x], g[k][y - (1 << k) + 1]);
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i) a[i]++;
	
	lg[1] = 0;
	for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
	for(int i = 1; i <= n; ++i) f[0][i] = g[0][i] = a[i];
	for(int k = 1; k < 20; ++k)
		for(int i = 1; i + (1 << k) - 1 <= n; ++i)
			f[k][i] = max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]),
			g[k][i] = min(g[k - 1][i], g[k - 1][i + (1 << (k - 1))]);
	for(int i = 2; i < k; ++i) if(a[i - 1] > a[i]) S.insert(i);
	set<pii> R;
	for(int i = 1; i < k; ++i) add(a[i], 1);
	for(int i = 1; i + k - 1 <= n; ++i) {
		int j = i + k - 1;
		if(a[j - 1] > a[j]) S.insert(j);
		add(a[j], 1);
//		printf("i = %d\n", i);
		if(S.empty()) R.emplace(0, 0);
		else {
			int x = *S.begin() - 1, y = *S.rbegin();
			int mn = qmin(x, y), mx = qmax(x, y);
//			printf("%d %d %d %d\n", x, y, mn, mx);
			R.emplace(i + sum(mn - 1), j - (j - i + 1 - sum(mx)));
//			printf("%d %d\n", i + sum(mn - 1), j - (j - i + 1 - sum(mx)));
		}
		if(a[i] > a[i + 1]) S.erase(i + 1);
		add(a[i], -1);
	}
	cout << R.size() << endl;
	return 0;
}



Measured memory_bytes: 43264
#include <iostream>
//#include <vector>
#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main() {
    string s;
    LL ans=700;
    cin >> s;
    for(LL i=0; i<3; i++){
        if(s[i]=='o'){
            ans+=100;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3600
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		sc.close();
		sc = null;
		int ans = a <= 5 ? 0 : (a <= 12 ? b /2 : b);
		System.out.println(ans);
	}
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
//No change above here

const ll maxi = 2 * 1e5 + 5;
ll mod = 1e9+7;
double pi = 3.141592653589793238;

//function for power
ll power(ll x, ll n) {
	ll res = 1;
	x %= mod;
	while (n) {
		if (n & 1)
			res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}

ll sum_digits(ll n)
{
	ll ret = 0;
	while (n)
	{
		ret += n % 10;
		n /= 10;
	}
	return ret;
}

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

ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}

ll max_subarray(vector<int>& v)
{
	if (v.empty())
		return 0;
	ll glob = v[0], loc = v[0];
	for (int i = 1; i < v.size(); ++i)
	{
		loc = max(v[i] + 0LL, loc + v[i]);
		glob = max(loc, glob);
	}
	return glob;
}

long long num_digits(long long x)
{
	long long ans = 0;
	while (x)
	{
		++ans;
		x /= 10;
	}
	return ans == 0 ? 1 : ans;
}

vector<int> topological_sort(vector<vector<int>>& graph, int n, vector<int>& indegree)
{
	vector<int> ans;
	stack<int> s;
	for (int i = 0; i < n; ++i)
		if (indegree[i] == 0)
			s.push(i);
	while (!s.empty())
	{
		int x = s.top();
		s.pop();
		ans.push_back(x);
		for (auto& adj : graph[x])
			if (--indegree[adj] == 0)
				s.push(adj);
	}
	return ans;
}

ll dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

ll p, q;
bool valid(ll i, ll j) { return i >= 1 && i <= p && j >= 1 && j <= q; }


//declare needed things here

//cabacc
//abc
int main()
{
	IOS;
	ll n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}
	//find the gcd of all elements
	ll gcd_all = v[0];
	for (int i = 1; i < n; ++i)
	{
		gcd_all = gcd(gcd_all, v[i]);
	}
	//if gcd of all is greater than 1 then not prime
	if (gcd_all > 1)
	{
		cout << "not coprime" << endl;
		return 0;
	}
	//taking the factors of all elements and saving it
	map<int, int> m;
	bool prm = true;
	for (int i = 0; i < n; ++i)
	{
		map<int, int> cur_m;
		int num = v[i];
		for (int j = 2; j * j <= num; ++j)
		{
			if (num % j==0)
			{
				cur_m[j]++;
				cur_m[num / j]++;
			}
		}
		cur_m[num]++;
		for (auto& j : cur_m)
		{
			if (m[j.first] > 0 && j.first>1)
			{
				prm = false;
				break;
			}
			m[j.first] += 1;
		}
		if (!prm)
			break;
	}
	if (prm)
		cout << "pairwise coprime";
	else
		cout << "setwise coprime";
	return 0;
}


Measured memory_bytes: 7292
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
#define LL long long
#define INF 0x3f3f3f3f

const int MAXN = 1e2 + 5;
const LL MOD = 1e9+7;

int a[2][MAXN];

int main() 
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    int n;
    cin >> n;
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int sum = 0;
        for(int j = 0; j <= i; j++)
            sum += a[0][j];
        for(int j = i; j < n; j++)
            sum += a[1][j];
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

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

int main()
   {
     ll n,a,b,i,cnt=0;;
     cin >> n >> a >>b;
     cnt=(n/(a+b))*a;
     n=n%(a+b);
     if(n==0)
     {
         cout << cnt;
         return 0;
     }
     if(n <a)
        cout << cnt+n;
     else
            cout << cnt+a;
   }


Measured memory_bytes: 256
N,M = list(map(int, input().split()))
ps = []
for i in range(M):
    p, s = input().split()
    ps.append([int(p), s])

ac = {}
wa = {}
for i in range(M):
    if ps[i][1] == 'AC':
        if not ac.get(ps[i][0]):
            ac[ps[i][0]] = 1
    else:
        if not ac.get(ps[i][0]):
            wa[ps[i][0]] = wa.get(ps[i][0], 0)
            wa[ps[i][0]] += 1

ansac = len(ac.keys())
answa = 0
for k in wa.keys():
    if ac.get(k):
        answa += wa[k]

print(ansac, answa)

Measured memory_bytes: 31236
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main()
{
  set<int>s;
  int n,x;;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>x;
    s.insert(x);
  }
  cout<<s.size();
  return 0;
}

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

const int mxn = 1e5 + 5;
long long n, a[mxn], sfx[mxn];

int main() {
	cin >> n;
	for (int i=0; i<=n; i++) {
		cin >> a[i];
	}
	for (int i=n; i>=0; i--) {
		sfx[i] = sfx[i + 1] + a[i];
	}
	long long nodes = 1, ans = 0;
	for (int i=0; i<=n; i++) {
		ans += nodes;
		if (a[i] > nodes) {
			cout << -1 << '\n';
			return 0;
		}
		nodes = min(sfx[i + 1], 2 * (nodes - a[i]));
	}
	cout << ans << '\n';
}

Measured memory_bytes: 5092
#include<bits/stdc++.h>
using namespace std;
set<int> con;
int main()
{
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(con.find(x)!=con.end())
            con.erase(con.find(x));
        else
            con.insert(x);
    }
    printf("%d\n",con.size());
    return 0;
}

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

int main(){
  int r;
  cin >> r;
  if(r<1200) cout << "ABC" << endl;
  else if(r<2800) cout << "ARC" << endl;
  else cout << "AGC" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.Stream;

public class Main {//ここが Main になっている
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line1;
        int[] k_n_array = new int[2];
        line1 = sc.nextLine();
        String[] strArray = line1.split("");
        // for (int i = 0; i < strArray.length; i++) {// // "strArray"を1文字ずつ表示
            // System.out.println("strArrayの要素番号" + i + "の時：" + strArray[i]);
        // }
        int count=0;
        for (int i = 0; i < strArray.length; i++) {
            // System.out.println("strArrayの要素番号" + i + "の時：" + strArray[i]);
            // System.out.println(i % 2 == 0);
            // System.out.println(strArray[i]);
            // System.out.println(strArray[i].equals("0"));
            if (i % 2 == 0 & strArray[i].equals("0")){
                // System.out.println("a");
                count++;
            }
            if (i % 2 == 1 && strArray[i].equals("1")){
                // System.out.println("b");
                count++;
            }
        }
        int another = strArray.length - count;
        if (count >= another){
            System.out.println(another);
        }
        else{
            System.out.println(count);
        }
    }
}


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

int kakui(int k){
  int sum = 0;
  sum += k / 10000;
  sum += (k % 10000) / 1000;
  sum += (k % 1000) / 100;
  sum += (k % 100) / 10;
  sum += k % 10;

  return sum;
}
int main(){
  int n;
  int min = 100000000;
  cin >> n;
  for(int a = 1;a <= n-1;a++){
    int b = n - a;
    int c = kakui(a) + kakui(b);
    if(c < min) min = c;
  }

  printf("%d\n", min);

  return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split(" "))
s = [input() for i in range(h)]

for y in range(h):
	for x in range(w):
		if s[y][x] == "#":
			is_have_hash = False
			for adjust_y, adjust_x in ((0, 1), (1, 0), (0, -1), (-1, 0)):
				if 0 <= y+adjust_y < h and 0 <= x+adjust_x < w:
					if s[y+adjust_y][x+adjust_x] == "#":
						is_have_hash = True
						break
			if not is_have_hash:
				print("No")
				exit()
print("Yes")

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

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

    string s;
    cin >> s;

    string ans;
    ans = s[0] + to_string(s.size() - 2) + s[s.size() - 1];

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}

int32_t N;
int32_t w[3000];
int32_t v[3000];

int32_t dp[3000][10001];
int32_t func(int i, int32_t W)
{
	if (W < 0) {
		return -2000000000;
	}
	if (i == N) {
		return 0;
	}
	if (dp[i][W] != -1) {
		return dp[i][W];
	}

	return dp[i][W] = std::max(func(i + 1, W), func(i + 1, W - w[i]) + v[i]);
}


int main()
{
	fill_all(dp, -1);
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	int32_t W;
	in >> N>>W;
	int32_t w_iter = 0;
	for (int32_t i = 0; i < N; i++)
	{
		int32_t tmpw, tmpv;
		int32_t m;
		in  >> tmpv >> tmpw;
		in >> m;
		auto w_iter_old = w_iter;

		w[w_iter] = tmpw;
		v[w_iter] = tmpv;
		++w_iter;

		int32_t count = 1;
		while (m >= ((1<< (count+1)) - 1)) {
			w[w_iter] = w[w_iter - 1] * 2;
			v[w_iter] = v[w_iter - 1] * 2;
			if (w[w_iter] > W) { m = 0; count = 0; break; }
			++w_iter;
			++count;
		}
		m = m - ((1 << (count)) - 1);
		while (m > 0) {
			if (m & 1) {
				w[w_iter] = tmpw;
				v[w_iter] = tmpv;
				++w_iter;
			}
			tmpw *= 2;
			tmpv *= 2;
			if (tmpw > W) { break; }
			m /= 2;
		}

		assert(w_iter - w_iter_old <= 30);
	}
	assert(w_iter <= 3000);
	N = w_iter;

	out << func(0, W) << endl;


	return 0;
}
#endif



Measured memory_bytes: 120512
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	long n,count=0,flag=0,m,mx=0;
	cin >> n ;

	vector<string> s(n);
	
	for (int i = 0; i < n; i++) {
		cin >> s.at(i);
	}
	cin >> m;

	vector<string> t(m);

	for (int i = 0; i < m; i++) {
		cin >> t.at(i);
	}

	for (int i = 0; i < n; i++) {
		count = 0;
		for (int j = 0; j < n; j++) {
			if(s.at(i) == s.at(j))count++;
		}
		for (int j = 0; j < m; j++) {
			if (s.at(i) == t.at(j))count--;
		}
		mx = max(mx, count);

	}

	cout << mx << endl;

	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);
    String s = sc.next();
    int n = s.length();
    int ans = 0;
    for(int i = 0; i < n; i++){
      for(int j = n; j > i;j--){
        if(s.substring(i, j).matches("[ACGT]*")){
          int l = s.substring(i, j).length();
          if(l > ans){
            ans = l;
          }
        }
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 22612
#include <iostream>
#include <bits/stdc++.h>
#define loop(N) for(int i=0;i<N;i++)
#define vi vector<int>
#define vs vector<string>
#define vl vector<long long int>
#define vpi vector<pair<int,int>>
#define msi map<string,int>
#define mil map<int,long long int>
#define lli long long int
#define plli pair<lli,lli>
using namespace std ;
void ps(string i){
    cout << i << endl;
}

template <class T>
void pt(T s){
    cout << s << endl;
}

void pi(int i){
    cout << i << endl;
}

template <class T>
void pv(vector<T> v){
    loop(v.size()){
        pt<T>(v[i]);
    }
}
/*********************************reused****************************/

int main()
{
    int n,k;
    cin >>n>>k;
    int ans = 1;
    loop(n){
        ans = min(ans+k,2*ans);
    }
    cout<< ans<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const ll MOD = 1000000007;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int n, m;
vector<pair<int, int> > p[100050];

string makeStr(int i, int j) {
	string s = to_string(i);
	if(s.size() < 6) {
		s = string(6-s.size(), '0') + s;
	}
	string t = to_string(j);
	if(t.size() < 6) {
		t = string(6-t.size(), '0') + t;
	}
	return s + t;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> n >> m;
	rep(i,0,m) {
		int a, b;
		cin >> a >> b;
		p[a].pb(mp(b,i));
	}
	rep(i,0,n+1) {
		if(p[i].size()) {
			sort(all(p[i]));
		}
	}
	vector<string> ret(m);
	rep(i,0,n+1) {
		rep(j,0,sz(p[i])) {
			int idx = p[i][j].S;
			ret[idx] = makeStr(i,j+1);
		}
	}
	rep(i,0,m) {
		cout << ret[i] << '\n';
	}
	return 0;
}


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

using namespace std;

int main(void){
  int a,b,c;
  cin >> a >> b >> c;
  int check=a*100+b*10+c;
  if(check%4==0){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

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

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------


int main(){
char b;
cin>>b;
if(b=='A'){
    cout<<"T"<<endl;
}
if(b=='C'){
    cout<<"G"<<endl;
}
if(b=='T'){
    cout<<"A"<<endl;
}
if(b=='G'){
    cout<<"C"<<endl;
}
}









Measured memory_bytes: 256
#include <stdio.h>

int bubblesort(int [100], int N);

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

int bubblesort(int A[100], int N){
  int flag = 1, count=0, v, j;
  while (flag){
    flag = 0;
    for(j=N-1;j>=1;j--){
      if(A[j] < A[j-1]){
	v=A[j];
	A[j]=A[j-1];
	A[j-1]=v;
	count++;
	flag = 1;
      }
    }
  }
  return count;
}



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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






long long int gcd(long long int a,long long int b)
{
 
  long long int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  long long int n,k,l,r;
  cin>>n>>k;
  vector<long long int> v(n);
  rep(i,n) cin>>v[i];
  rep(i,n){
    if(v[i]==1) l=i;
  }
  r=n-l-1;
  cout<<(l+r+k-2)/(k-1)<<endl;
}
///////////////////////////



Measured memory_bytes: 1024
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
using namespace std;

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

typedef long long ll;
typedef unsigned long long int ulli;

const ll INF = ll(1e18) + 1;

//--------------------------------------------------

ulli gcd(ulli a, ulli b) {
	return (b <= 0) ? a : gcd(b, a % b);
}

ulli lcm(ulli a, ulli b) {
	return a * b / gcd(a, b);
}



//---------------------------------------------------



void Main()
{
	char c; cin >> c;
	cout << (char)((int)c + 1) << endl;

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

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
a.append(0)
cnt = 0
for i in range(n+1):
  cnt += abs(a[i]-a[i+1])
for i in range(1,n+1):
  ans = cnt
  if a[i-1] <= a[i] <= a[i+1]:
    print(ans)
  elif a[i+1] <= a[i] <= a[i-1]:
    print(ans)
  else:
    ans -=2*min(abs(a[i]-a[i-1]),abs(a[i]-a[i+1]))
    print(ans)

Measured memory_bytes: 14172
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        BigDecimal A = new BigDecimal(sc.next());
        BigDecimal B = new BigDecimal(sc.next());

        System.out.println(A.multiply(B).longValue());
        sc.close();

    }
}


Measured memory_bytes: 35992
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t,ans = "Yes";
    cin >> s >> t;
    bool eql = true;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    if(s>=t) ans = "No";
    cout << ans << endl;
    return 0;
}



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

using namespace std;
#define sc second;
#define fr first;
int mod = pow(10,9)+7;
int main()
{
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   int n;
   cin>>n;
   string s ="";
   int i =0;
   if(n==0)
   {
   	  cout<<0;
   }
   while(n!=0)
   {
   	  if(abs(n)%2)
   	  {
   	  	 s+='1';
   	  	 if(i%2==0)
   	  	 {
   	  	 	n = (n-1)/2;
   	  	 }
   	  	 else
   	  	 {
   	  	 	n = (n+1)/2;
   	  	 }
   	  }
   	  else
   	  {
   	  	s+='0';
   	  	n/=2;
   	  }

   	  i++;
   }

   reverse(s.begin(),s.end());
   cout<<s;
}	

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int n,v[25],c[25],i,sol=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	for(i=0;i<n;i++){
		scanf("%d",&c[i]);
		if(v[i]-c[i] > 0) sol+=v[i]-c[i];
	}
	
	printf("%d",sol);
	return 0;
}

Measured memory_bytes: 128
#
# abc069 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 10 100"""
        output = """Yes"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 2 3 4"""
        output = """No"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3
1 4 1"""
        output = """Yes"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """2
1 1"""
        output = """No"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """6
2 7 1 8 2 8"""
        output = """Yes"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    Q = 0
    E = 0
    O = 0
    for a in A:
        if a % 4 == 0:
            Q += 1
        elif a % 2 == 0:
            E += 1
        else:
            O += 1

    if N-2*Q <= 0 or (N-2*Q) == 1 or N-2*Q == E:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 27448
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

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

using namespace std;

const long long MOD = 1000000007;


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

	string s, t;
	cin >> s >> t;

	cout << t << s << "\n";

	return 0;
}


Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))

def gcd(x,y):
    if max(x, y) % min(x, y) == 0:
        return min(x,y)
    else:
        return gcd ( max(x,y) % min (x,y) , min(x,y))

def lcm(x,y):
    return x * y // gcd(x,y)

ans = A[0]
for i in range(n-1):
    ans = lcm(ans, A[i+1])

print(ans)


Measured memory_bytes: 5600
using System;

class ABC_169_B
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        long[] A = new long[N];

        string[] input = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++)
        {
            A[i] = long.Parse(input[i]);
            if(A[i]==0)
            {
                Console.WriteLine(0);
                return;
            }
        }

        long[] B = new long[N];
        B[0] = A[0];
        for (int i = 1; i < N; i++)
        {
            B[i] = A[i] * B[i-1];
            if (B[i] > 1000000000000000000L)
            {
                Console.WriteLine(-1);
                return;
            }

            if(long.MaxValue/A[i] < B[i-1])
            {
                Console.WriteLine(-1);
                return;
            }
        }

        Console.WriteLine(B[N-1]);
    }
}

Measured memory_bytes: 40908
#include <iostream>
  #include <iomanip>
  #include <algorithm>
  #include <cmath>
  #include <queue>
  #include <list>
  #include <limits>
  #include <string>
  #include <vector>
  #include <stack>
  using namespace std;


  int check(int sum,int edge){
    if(edge < sum - edge) return 1;//できれば1
    return 0;
  }

  int main(){
    int n = 0;
    cin >> n;
    std:vector<int> edges;
    int edge = 0;
    int edgesum = 0;
    for(int i = 0; i < n;i++){
      cin >> edge;
      edgesum += edge;
      edges.push_back(edge);
    }

  int c = 1;
    for(int edge:edges){
      c = c * check(edgesum,edge);
    }
  if(c == 1){
    cout << "Yes";
  }else{
    cout << "No";
  }
  }

Measured memory_bytes: 256
n,m = map(int,input().split())
s_c_list=[list(map(int,input().split())) for _ in range(m)]

ans_list = [0 for _ in range(n)]

cant_count = 0
for i in range(len(s_c_list)):
    if s_c_list[i][0] == 1 and s_c_list[i][1] == 0:
        if len(ans_list) != 1: # 0対策
            cant_count += 1
    else:
        if ans_list[s_c_list[i][0] - 1] == 0:
            ans_list[s_c_list[i][0] - 1] = s_c_list[i][1]
        elif ans_list[s_c_list[i][0] - 1] != s_c_list[i][1]:
            cant_count += 1

ans_list_final = [0 for _ in range(n)]
non0_count = 0

if len(ans_list) == 1 and ans_list[0] == 0:
    print('0')
else:
    for i in range(len(ans_list)):
        if i == 0 and ans_list[0] == 0:
            ans_list_final[0] = '1'
        else:
            ans_list_final[i] = ans_list[i]
        
    s = ''
    for i in range(len(ans_list_final)):
        s += str(ans_list_final[i])

    if cant_count == 0:
        print(s)
    else:
        print('-1')

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

int main(void){
    int n;
    cin >> n;
    vector<int> order(n), happy(n), bonus(n-1);
    for(int i=0;i<n;i++){cin >> order[i]; order[i]--;}
    for(int i=0;i<n;i++) cin >> happy[i];
    for(int i=0;i<n-1;i++) cin >> bonus[i];

    int ans = 0;
    for(int i=0;i<n-1;i++){
        ans += happy[order[i]];
        if(order[i]+1 == order[i+1]) ans += bonus[order[i]];
    }
    ans += happy[order[n-1]];

    cout << ans << endl;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

template<typename T>
bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

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

	string S=in<string>(),T=in<string>();
	int SN=S.size(),TN=T.size();
	vector<vector<ll>> dp(SN+1,vector<ll>(TN+1,1LL<<60));
	REP(i,SN+1) dp[i][0]=i;
	REP(i,TN+1) dp[0][i]=i;

	REP(i,SN){
		REP(j,TN){
			int cost = (S[i]==T[j]) ? 0 : 1;
			chmin(dp[i+1][j+1],dp[i][j]+cost);
			chmin(dp[i+1][j+1],dp[i+1][j]+1);
			chmin(dp[i+1][j+1],dp[i][j+1]+1);
		}
	}

	out(dp[SN][TN]);
	return 0;
}



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

int main(void){
    int i,j,N,M;
    scanf("%d",&N);
    char s[N][11];
    int s_n[N];
    int prev,max = -2147483648;
    for(i=0;i<N;i++){
        scanf("%s",s[i]);
        s_n[i] = 0;
    }
    scanf("%d",&M);
    char t[M][11];
    for(i=0;i<M;i++){
        scanf("%s",t[i]);
    }
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            if(0 == strcmp(s[i],s[j])){
                s_n[i]++;
            }
        }
        for(j=0;j<M;j++){
            if(0 == strcmp(s[i],t[j])){
                s_n[i]--;
            }
        }
    }
    for(i=0;i<N;i++){
        prev=max;
        max = s_n[i];
        if(prev>max){
            max = prev;
        }
    }
    if(max>=0){
        printf("%d\n",max);
    }
    else{
        printf("0\n");
    }
    return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define POW(n) ((n)*(n))
#define ALL(a) (a).begin(),(a).end()
#define cerr if(false) cerr
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

void solve(string AtCoder, string s, string Contest){
	cout << "A" << s[0] << "C" << endl;
}



int main(){	
	ios::sync_with_stdio(false);
	string AtCoder;
	string Contest;
	string s;
	cin >> AtCoder;
	cin >> s;
	cin >> Contest;
	solve(AtCoder, s, Contest);
	return 0;
}


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

char shift(const char& t, int n) {
//  'A' => 65 => 0
//  'Z' => 90 => 25
  int c = (t - 65 + n)%26 + 65;
  return static_cast<char>(c);
}

int main(int argc, char** argv) {
  int N;
  std::cin >> N;
  std::string s;
  std::cin >> s;
  std::for_each(s.begin(), s.end(), [=](auto& e){e = shift(e, N);});
  std::cout << s << '\n';
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
using namespace std;


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


int main(){
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i, n) cin >> d[i];
  sort(d.begin(), d.end());

  int ans = 1;
  int dtmp = d[0];
  for(int i = 1; i < d.size(); ++i){
    if(dtmp == d[i])  continue;
    else {
      dtmp = d[i];
      ++ans;
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
#include <cstdio> 
#include <vector> 
#include <algorithm> 
using namespace std; 
typedef long long ll; 
#define rep(i,n) for(int i=0;i<n;i++)
int N,M; 
int P[100000],Y[100000]; 
vector <int> yd[100001];
int main() { 
	scanf("%d%d",&N,&M); 
	rep(i,M)scanf("%d%d",&P[i],&Y[i]),yd[P[i]].push_back(Y[i]); 
	rep(i,N)sort(yd[i+1].begin(),yd[i+1].end()); 
	rep(i,M)printf("%012lld\n",ll(P[i])*1000000+int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin() )  +  1);
} 

Measured memory_bytes: 7680
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int n=in();
	int a[10];
	string b[10];
	while(n--){
		int i;
		for(i=0;i<9;i++){
			cin>>a[i];
		}
		for(i=0;i<9;i++){
			cin>>b[i];
		}
		int per[]={0,1,2,3,4,5,6,7,8};
		bool win=false;
		do{
//cout<<per[0]<<" "<<per[1]<<" "<<per[2]<<" "<<per[3]<<" "<<per[4]<<" "<<per[5]<<" "<<per[6]<<" "<<per[7]<<" "<<per[8]<<endl;
			int set=0;
			if(a[per[0]]==a[per[1]]&&a[per[1]]==a[per[2]]||a[per[0]]+1==a[per[1]]&&a[per[1]]+1==a[per[2]]){
				if(b[per[0]]==b[per[1]]&&b[per[1]]==b[per[2]])set++;
			}
			if(a[per[3]]==a[per[4]]&&a[per[4]]==a[per[5]]||a[per[3]]+1==a[per[4]]&&a[per[4]]+1==a[per[5]]){
				if(b[per[3]]==b[per[4]]&&b[per[4]]==b[per[5]])set++;
			}
			if(a[per[6]]==a[per[7]]&&a[per[7]]==a[per[8]]||a[per[6]]+1==a[per[7]]&&a[per[7]]+1==a[per[8]]){
				if(b[per[6]]==b[per[7]]&&b[per[7]]==b[per[8]])set++;
			}
//cout<<set<<endl;
			if(set==3)win=true;
		}while(next_permutation(per,per+9));
		cout<<(win?1:0)<<endl;
	}
	return 0;
}

Measured memory_bytes: 960
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a; i < n; i++)
#define per(i,n,a) for (int i = n - 1; i >= a; i--)
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = s.size(), len = s.size();
    rep(i, 0, s.size()) {
        if (s[i] != s[i + 1]) {
            ans = min(ans, max(i + 1, len - i - 1));
        }
    }
    cout << ans << endl;
}


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

typedef long long LL;
const int Mod = 1000000007;
const int MN = 200005, MM = 200005;

int N, M, K;
char S[MM];
int A[MN], B[MN], Ans;

int main() {
	scanf("%d%d%s", &N, &M, S + 1);
	K = 0x3f3f3f3f;
	int isfirst = 1, len = 0;
	for (int i = 1; i <= M; ++i) {
		if (S[i] != S[1]) {
			if (isfirst || len & 1) K = std::min(K, len / 2 + 1);
			isfirst = len = 0;
		} else ++len;
	}
	if (isfirst) {
		int X1 = 1, X2 = 0;
		for (int i = 1; i <= N; ++i) {
			X2 -= (X2 = X1 + X2) >= Mod ? Mod : 0;
			X1 += (X1 = X2 - X1) < 0 ? Mod : 0;
		}
		printf("%lld\n", (2ll * X1 + X2) % Mod);
		return 0;
	}
	if (N & 1) return puts("0"), 0;
	N /= 2;
	K = std::min(K, N);
	A[0] = B[0] = 1;
	for (int i = 1; i <= N; ++i) {
		A[i] = B[i - 1];
		if (i > K) A[i] += (A[i] -= B[i - K - 1]) < 0 ? Mod : 0;
		B[i] -= (B[i] = B[i - 1] + A[i]) >= Mod ? Mod : 0;
	}
	for (int i = 1; i <= K; ++i)
		Ans = (Ans + 2ll * i * A[N - i]) % Mod;
	printf("%d\n", Ans);
	return 0;
}


Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int Max=0;
    for(int i=0;i<n;i++){
        int a,cnt=0;
        for(int j=0;j<m;j++){
            cin>>a;
            if(a)cnt++;
        }
        Max=max(Max,cnt);
    }
    cout<<Max<<endl;
}

Measured memory_bytes: 1160
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

inline double sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
// }}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	rep(i,n){
		cin >> h[i];
	}
	sort(all(h));
	int minv = INF;
	for(int i = 0;i + k <= n;++i){
		minv = min(minv,h[i+k-1] - h[i]);
	}
	cout << minv << '\n';
	return 0;	
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const ll LLINF = 1e16;

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];

    vector<vector<ll>> dp(N+1, vector<ll>(W+1, -1));
    dp[0][0] = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= W; j++) {
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            if (j+w[i] <= W) dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i]);
        }
    }

    ll ans = -LLINF;
    for(int i = 0; i <= W; i++) {
        ans = max(ans, dp[N][i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 80256
n = int(input())
a_list = [int(i) for i in input().split()]

dp = [[0 for i in range(2)] for i in range(n)]

dp[0][0] = a_list[0]
dp[0][1] = -1*a_list[0] 

for i in range(1, n-1):
    a = a_list[i]
    dp[i][0] = max(dp[i-1][0] + a, dp[i-1][1] - a)
    dp[i][1] = max(dp[i-1][0] - a, dp[i-1][1] + a)
dp[n-2][1] -= a_list[n-1]
dp[n-2][0] += a_list[n-1]
ans = max(dp[n-2][0], dp[n-2][1])

print(ans)

Measured memory_bytes: 27040
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxm=2e6+5;
char s[maxm];
int n;
struct SAM{
    int ch[maxm][26];
    int fa[maxm],l[maxm];//l[]是等价类的最长字符串长度len
    int last=1,tot=1;//tot是节点数量
    //
    int lc[maxm],rc[maxm];
    int cnt[maxm];
    int idx[maxm];
    int solve(){
        //基数排序
        for(int i=0;i<=tot;i++)cnt[i]=0;
        for(int i=1;i<=tot;i++)cnt[l[i]]++;
        for(int i=1;i<=tot;i++)cnt[i]+=cnt[i-1];
        for(int i=1;i<=tot;i++)idx[cnt[l[i]]--]=i;
        //逆向拓扑
        for(int i=tot;i>=1;i--){
            int x=idx[i];
            if(!lc[fa[x]]||lc[x]<lc[fa[x]]){
                lc[fa[x]]=lc[x];
            }
            if(!rc[fa[x]]||rc[x]>rc[fa[x]]){
                rc[fa[x]]=rc[x];
            }
        }
        //
        int ans=0;
        for(int i=1;i<=tot;i++){
            if(rc[i]-lc[i]>=l[i]){
                ans=max(ans,l[i]);
            }else{
                ans=max(ans,rc[i]-lc[i]);
            }
        }
        return ans;
    }
    //
    void add(int c,int pos){//传入s[i]-'a'而不是s[i]
        int p=last,np=++tot;last=np;l[np]=l[p]+1;
        for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
        if(!p)fa[np]=1;
        else{
            int q=ch[p][c];
            if(l[p]+1==l[q])fa[np]=q;
            else{
                int nq=++tot;l[nq]=l[p]+1;
                memcpy(ch[nq],ch[q],sizeof ch[q]);
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
            }
        }
        //记录最左和最右位置
        lc[np]=rc[np]=pos;
    }
    void init(){
        for(int i=1;i<=tot;i++){
            memset(ch[i],0,sizeof ch[i]);
            fa[i]=l[i]=0;
        }
        last=tot=1;
    }
}S;
signed main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    S.init();
    for(int i=1;i<=n;i++){
        S.add(s[i]-'a',i);
    }
    int ans=S.solve();
    cout<<ans<<endl;
    return 0;
}


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

template <typename InputIterator>
typename InputIterator::value_type
summation(InputIterator first, InputIterator last) {
  using T = typename InputIterator::value_type;
  T *p = new T();
  const auto sum = std::accumulate(first, last, *p);
  delete p;
  return sum;
}
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n, a, b;
  std::cin >> n >> a >> b;
  std::vector<int64_t> x(n);
  std::cin >> x;
  int64_t v = 0;
  for (int64_t i = 1; i < n; i++) {
    v += std::min(b, (x[i] - x[i - 1]) * a);
  }
  std::cout << v << std::endl;
  return 0;
}


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

int main(){
    int n; cin >> n;
    vector<int> b(n-1); 
    rep(i,n-1) cin >> b[i];
    vector<int> a(n);
    a[0] = b[0]; a[n-1] = b[n-2];
    int sum = a[0] + a[n-1];
    for(int i=0; i<n-2; i++){
        a[i+1] = min(b[i],b[i+1]);
        sum+=a[i+1];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3620
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

constexpr int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
constexpr int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vi cnt(m, 0);
	REP(i, n) {
		int k; cin >> k;
		REP(j, k) {
			int a;
			cin >> a;
			cnt[a - 1]++;
		}
	}
	int ans = 0;
	REP(i, m) {
		if (cnt[i] == n)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 892
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int m;
int n;
int f;
int main()
{
	cin>>n;
	m=n;
	for(int i=0;true;i++)
	{
		f+=m%10;
		m/=10;
		if(m==0)break;
	}
	if(n%f==0)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

//#define int long long

using namespace std;

int grid[53][53];

struct s
{
    int x;
    int y;
};

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

    int w, h;
    cin >> h >> w;

    string str;
    int white = 0;

    for (int hh = 0; hh < h; ++hh)
    {
        cin >> str;

        for (int ww = 0; ww < w; ++ww)
        {
            grid[hh + 1][ww + 1] = str[ww] == '#' ? -1 : 0;
            white += (str[ww] == '#' ? 0 : 1);
        }
    }
    //マップの周りを埋める
    for (int ww = 0; ww < w + 2; ++ww)
    {
        grid[0][ww] = -1;
        grid[h + 1][ww] = -1;
    }

    //マップの周りを埋める
    for (int hh = 0; hh < h + 2; ++hh)
    {
        grid[hh][0] = -1;
        grid[hh][w + 1] = -1;
    }

    queue
 qu;

    //スタート地点をqueueに積む
    qu.push({ 1,1 });

    for (;;)
    {
        if (qu.empty())
        {
            cout << -1 << endl;
            return 0;
        }

        //1番後ろを取り出す
        s s = qu.front();
        qu.pop();
        const auto n = grid[s.y][s.x];

        //cout << s.x << "<x | y> " << s.y << " n:" << s.n << endl;

        int x = 0, y = 0;
        x = s.x - 1;
        y = s.y - 0;
        if (grid[y][x] == 0)
        {
            qu.push({ x,y});
            grid[y][x] = n+1;
        }

        x = s.x - 0;
        y = s.y - 1;
        if (grid[y][x] == 0)
        {
            qu.push({ x,y });
            grid[y][x] = n+1;
        }

        x = s.x + 1;
        y = s.y + 0;
        if (grid[y][x] == 0)
        {
            qu.push({ x,y });
            grid[y][x] = n+1;
        }

        x = s.x + 0;
        y = s.y + 1;
        if (grid[y][x] == 0)
        {
            qu.push({ x,y });
            grid[y][x] = n+1;
        }

        //ゴールに値が入ったら終わり
        if (s.y == h && s.x == w)
        {
            break;
        }

        //for (int hh = 0; hh < h + 2; ++hh)
        //{
        //    for (int ww = 0; ww < w + 2; ++ww)
        //    {
        //        cout << grid[hh][ww] + 1;
        //    }
        //    cout << '\n';
        //}
        //cout << '\n';
    }

    cout << white - grid[h][w] - 1 << endl;


    //デバッグ出力
    /*
    for (int h = 0; h < h + 2; ++h)
    {
        for (int w = 0; w < w + 2; ++w)
        {
            cout << grid[h][w] + 1;
        }
        cout << '\n';
    }
    */
}


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

static class NagataKanaIsAGenius {
    public static void Main() {
        int a=0,b=0;
        foreach(char c in Console.ReadLine()){
            if(c=='0')a++;
            if(c=='1')b++;
        }
        Console.WriteLine(Math.Min(a,b)*2);
    }
}


Measured memory_bytes: 13148