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

int cost[] = {0,2,5,5,4,5,6,3,7,6};
bool d[10] = {};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int a;
        cin >> a;
        d[a] = 1;
    }

    vector<string> dp(n+1, "");
    for (int i=1; i<10; i++) {
        if ( !d[i] ) continue;
        for (int j=cost[i]; j<=n; j++) {
            if ( j-cost[i]>0 && dp[j-cost[i]]=="" ) continue;
            string s=dp[j-cost[i]]+to_string(i);
            sort(s.rbegin(), s.rend());
            if ( s.length()==dp[j].length() ) {
                dp[j]=max(s, dp[j]);
            } else if ( s.length()>dp[j].length() ) {
                dp[j]=s;
            }
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

Measured memory_bytes: 25856
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int> >;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define rrep(i,m, n) for(int i = m; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<int>(n,a)));
typedef long long ll;
const int INF = 2000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007LL;
typedef unsigned int uint;

int main(){
  ll ans=0;
  string s;
  std::cin >> s;
  int le=s.size()-1;
  for(ll bit=0;bit<(1<<s.size()-1);bit++){
    ll dum=0;
    std::vector<int>a;
    a.pb(0);
    rep(i,le){
      if(bit&(1<<i))a.pb(i+1);
    }
    a.pb(le+1);
    rep(i,a.size()-1){
  //    std::cout <<s.substr(a[i],a[i+1]-a[i])<< ' ';
      dum+=stoll(s.substr(a[i],a[i+1]-a[i]));
    }
    ans+=dum;
  //  std::cout  << std::endl;
  }
  std::cout << ans << std::endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
    static void Main(string[] args){
    var ans=0;
    //複数
    var vals = Console.ReadLine().Split().Select(x => int.Parse(x)).ToList();
    int A=vals[0];
    int P=vals[1];
    ans=(A*3+P)/2;
    Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11220
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string X;
  cin >> X;
  stack<ll> s;
  for (int i = 0; i < X.size(); i++) {
    if (X[i] == 'S') {
      s.push(X[i]);
    } else if (s.empty() || s.top() == 'T') {
      s.push(X[i]);
    } else if (!s.empty() && s.top() == 'S') {
      s.pop();
    }
  }
  cout << s.size() << endl;
  return 0;
}

Measured memory_bytes: 5048
#include <bits/stdc++.h>
// https://www.irohabook.com/exp-2
// 1e9（10桁） は 2^26乗～2^27乗 であり、int(正負の2^16乗まで)では不可

using namespace std;

char N[200010]; // 文字列
int main()
{
	cin >> N;

	int len = strlen(N);
	int sum = 0;

	for (int i = 0; i < len; i++) {
		sum += N[i]-'0';
	}

	cout << ((sum%9==0)?"Yes":"No") << endl;
}

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

using ll = long long;

int main() {
  ll N;
  cin >> N;
  
  ll ans = 0;
  for (ll i = 1; i <= N; i++){
    ans += i;
    for(ll j = i+i; j<=N; j += i){
      ans += j;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>
#include <math.h>

int main(){
	int a[11][11], i, j, n;
	while(scanf("%d", &n) != 0){
		if(n == 0) break;
		for(i = 0; i <= n; i++){
			a[n][i] = 0;
			a[i][n] = 0;
		}
		for(i = 0; i < n; i++){
			for(j = 0; j < n; j++){
				scanf("%d", &a[i][j]);
				a[i][n] += a[i][j];
				a[n][j] += a[i][j];
			}
			a[n][n] += a[i][n];
		}
		for(i = 0; i <= n; i++){
			for(j = 0; j < n; j++){
				if(a[i][j] / 10000 < 1) printf(" ");
				if(a[i][j] / 1000 < 1) printf(" ");
				if(a[i][j] / 100 < 1) printf(" ");
				if(a[i][j] / 10 < 1) printf(" ");
				printf("%d", a[i][j]);
			}
			if(a[i][n] / 10000 < 1) printf(" ");
			if(a[i][n] / 1000 < 1) printf(" ");
			if(a[i][n] / 100 < 1) printf(" ");
			if(a[i][n] / 10 < 1) printf(" ");
			printf("%d\n", a[i][n]);
		}
	}
	return 0;
}

Measured memory_bytes: 604
N,K= (int(x) for x in input().split(' '))
N = [i for i in range(1,N+1)]
d_lst = []
for i in range(0,K):
    d = int(input())
    d_lst.append(d)
    A= [int(x) for x in input().split(' ')]
    N.extend(A)

print(len([x for x in set(N) if N.count(x) == 1]))

Measured memory_bytes: 9320
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

vector<vector<pair<int,int> > > v;

int main() {
    int n, p, q;
    while (cin >> n >> p >> q, n) {
        p = (p/100)*60+(p%100);
        q = (q/100)*60+(q%100);
        v.clear(); v.resize(n);
        int k, a, b;
        for (int i=0; i<n; ++i) {
            cin >> k;
            for (int j=0; j<k; ++j) {
                cin >> a >> b;
                a = (a/100)*60+(a%100);
                b = (b/100)*60+(b%100);
                v[i].push_back(make_pair(a, b));
            }
        }
        int ret = 0, c = 0;
        for (int t=p; t<q; ++t) {
            bool ok = false;
            for (int i=0; i<n; ++i) {
                bool ok2 = true;
                for (int j=0; j<(int)v[i].size(); ++j) {
                    if (v[i][j].first <= t && t < v[i][j].second) {
                        ok2 = false; break;
                    }
                }
                if (ok2) {
                    ok = true; break;
                }
            }
            c = (ok ? c+1 : 0);
            ret = max(ret, c);
        }
        cout << ret << endl;
    }
    return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

int st[200];
int sp;

bool isFull() {
	if(sp >= 200)
		return true;
	return false;
}

bool isEmpty() {
	if (sp <= 0)
		return true;
	return false;
}

void push(int d) {
	if (isFull()) {
		cout << "stack is full" << endl;
		return;
	}
	sp++;
	st[sp] = d;
}

int pop() {
	if (isEmpty()) {
		cout << "stack is empty" << endl;
		return -1;
	}
	int d = st[sp];
	sp--;
	return d;
}

int main(){
	sp = 0;
	string str;
	getline(cin, str);
	stringstream ss(str);
	char val[8];
	int acc;

	while (!ss.eof()){
		ss >> val;
		switch (val[0]) {
		case '*':
			push(pop() * pop());
			break;
		case '+':
			push(pop() + pop());
			break;
		case '-':
			acc = pop();
			push(pop() - acc);
			break;
		default:
			push(atoi(val));
			break;
		}
	}

	cout << pop() << endl;

	return 0;
}

Measured memory_bytes: 1216
#include <stdio.h>

int main(int argc, const char * argv[])
{

    int a[4];
    int b[4];
    while (scanf("%d", &a[0]) != EOF) {
        int i = 0, k = 0;
        int hit = 0;
        int blow = 0;
        for (i = 1; i < 4; i++) {
            scanf("%d", &a[i]);
        }
        for (i = 0; i < 4; i++) {
            scanf("%d", &b[i]);
        }
        for (i = 0; i < 4; i++) {
            for (k = 0; k < 4; k++) {
                if (a[i] == b[k]) {
                    if (i == k) {
                        hit++;
                    }
                    else {
                        blow++;
                    }
                }
            }
        }
        printf("%d %d\n", hit, blow);
        
    }
    return 0;
}

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

int main() {
    int n;
    cin>>n;
    int results[n][2];
    bool doublet = false;
    for(int i=0;i<n;i++) {
        cin>>results[i][0]>>results[i][1];
        if(results[i][0]!=results[i][1])
            continue;
        if(i>=2) {
            if(results[i-1][0]==results[i-1][1] and results[i-2][0]==results[i-2][1])
                doublet=true;
        }
    }
    if(doublet) cout<<"Yes\n";
    else cout<<"No\n";
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int m = sc.nextInt();
			int f = sc.nextInt();
			int r = sc.nextInt();
			if(m==-1 && f==-1 && r==-1) break;
			
			else if(m==-1||f==-1) System.out.println("F");
			else if(m+f>=80) System.out.println("A");
			else if(m+f>=65) System.out.println("B");
			else if(m+f>=50) System.out.println("C");
			else if(m+f>=30){
				if(r>=50) System.out.println("C");
				else System.out.println("D");
			}
			else System.out.println("F");
		}
	}
}

Measured memory_bytes: 19228
#include<iostream>

using namespace std;

int main() {
		long x;
		cin >> x;

		long cnt = 0;
		long y = 100;
		while(true) {
				cnt++;
				y = y + (y  * 0.01);
				if ( y >= x){
					   	cout << cnt << endl;
						break;
				}
		}				
}


Measured memory_bytes: 3632
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

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

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

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

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

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

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn primes(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];

    if n >= 1 {
        is_prime[1] = false;
    }
    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            let mut cur = i * i;
            while cur < n {
                is_prime[cur] = false;
                cur += i;
            }
        }
        i += 1;
    }
    is_prime
}

fn main() {
    input! {
        q: usize,
        lr: [(usize, usize); q],
    }
    let mut max_ = 0;
    for i in 0..q {
        max_ = max(max_, lr[i].1);
    }
    let ps = primes(max_);
    let mut cumsum_ = vec![0; ps.len()];
    for i in 1..ps.len() {
        if ps[i] && i % 2 == 1 {
            if ps[(i + 1) / 2] {
                cumsum_[i] += 1;
            }
        }
        cumsum_[i] += cumsum_[i - 1];
    }
    for (l, r) in lr {
        println!("{}", cumsum_[r] - cumsum_[l - 1])
    }
}


Measured memory_bytes: 6780
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

static void inputSentences(std::vector<std::string>& sentences, int n)
{
  //fflush(stdin);
  std::string inputSentence;
  getline(std::cin, inputSentence);
  for (int i = 0; i < n; i++) {
    getline(std::cin, inputSentence);
    sentences.push_back(inputSentence);
  }
}

//static void convertSentencesCore(const std::string& targetBase,
//                                 const char afterConvert,
//                                 int convertPos,
//                                 std::vector<std::string>& sentences)
//{
//  for (std::vector<std::string>::iterator it = sentences.begin();
//    it != sentences.end();
//    ++it) {
//    /* ?????¬ */
//    if (*it == targetBase) {
//      it->at(convertPos) = afterConvert;
//      continue;
//    }
//    if (it->size() <= targetBase.size()) {
//      continue;
//    }
//    while(true) {
//      int find;
//      std::string targetStr;
//      bool findFlg = false;
//      /* ?????? */
//      targetStr = " " + targetBase + " ";
//      find = it->find(targetStr);
//      if (find != std::string::npos) {
//        it->at(find + convertPos + 1) = afterConvert;
//        findFlg = true;
//      }
//      /* ?????? */
//      targetStr = targetBase + " ";
//      find = it->find(targetStr);
//      if (find == 0) {
//        it->at(convertPos) = afterConvert;
//        findFlg = true;
//      }
//      /* ????°? */
//      targetStr = " " + targetBase;
//      find = it->find(targetStr);
//      if (find == it->size() - targetBase.size() - 1) {
//        it->at(find + convertPos + 1) = afterConvert;
//        findFlg = true;
//      }
//      if (findFlg == false) {
//        break;
//      }
//    }
//  }
//}
//
//static void convertSentences(std::vector<std::string>& sentences)
//{
//  convertSentencesCore("Hoshino", 'a', 6, sentences);
//  convertSentencesCore("Hoshino,", 'a', 6, sentences);
//  convertSentencesCore("Hoshino.", 'a', 6, sentences);
//}

static void convertSentences(std::vector<std::string>& sentences)
{
  const std::string from = "Hoshino";
  const std::string to = "Hoshina";
  for (std::vector<std::string>::iterator it = sentences.begin();
    it != sentences.end();
    ++it) {
    while (true) {
      std::string::size_type find = it->find(from);
      if (find == std::string::npos) {
        break;
      }
      else {
        //it->at(find + 6) = 'a';
        it->replace(find, from.size(), to);
      }
    }
  }
}

static void outputSentences(std::vector<std::string>& sentences)
{
  for (std::vector<std::string>::iterator it = sentences.begin();
    it != sentences.end();
    ++it) {
    std::cout << *it << std::endl;
  }
}

int main(void)
{
  int n;
  std::vector<std::string> sentences;

  std::cin >> n;

  inputSentences(sentences, n);
  convertSentences(sentences);
  outputSentences(sentences);

  return 0;
}

Measured memory_bytes: 1224
# ABC071-C
N = int(input())
A = sorted(list(map(int, input().split())), reverse = True)

for i in range(N-1):
    if A[i] == A[i+1]:
        A[i+1] = 0
    elif A[i] != A[i+1]:
        A[i] = 0
A.sort(reverse = True)
print(A[0] * A[1])

Measured memory_bytes: 14252
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ATOrT solver = new ATOrT();
        solver.solve(1, in, out);
        out.close();
    }

    static class ATOrT {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            w.println(Math.min(s.nextInt() * s.nextInt(), s.nextInt()));
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21460
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
		int[] P = new int[N];
		int min = Integer.MAX_VALUE;
		int count = 0;
      
		for(int i=0; i<N; i++){
			P[i] = sc.nextInt();
			if(min>=P[i]){
				min = P[i];
				count++;
            }
        }
		System.out.println(count);
    }
}

Measured memory_bytes: 74908
using static System.Math;
using System.Collections.Generic;
using System;

public class Hello
{
    public static long a, b, c, d;
    public static Dictionary<long, long> dic;
    public static void Main()
    {
        var t = int.Parse(Console.ReadLine().Trim());
        while (t > 0)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = long.Parse(line[0]);
            a = long.Parse(line[1]);
            b = long.Parse(line[2]);
            c = long.Parse(line[3]);
            d = long.Parse(line[4]);
            dic = new Dictionary<long, long>();
            var ans = getAns(n);
            Console.WriteLine(ans);
            t--;
        }
    }
    static long getAns(long n)
    {
        if (n == 0) return 0;
        if (n == 1) return d;
        if (dic.ContainsKey(n)) return dic[n];
        var L2 = n / 2;
        var r2 = (n + 1) / 2;
        var L3 = n / 3;
        var r3 = (n + 2) / 3;
        var L5 = n / 5;
        var r5 = (n + 4) / 5;
        var res = long.MaxValue;
        if (n < res / d) res = n * d;
        res = Min(res, Abs(L2 * 2 - n) * d + a + getAns(L2));
        res = Min(res, Abs(r2 * 2 - n) * d + a + getAns(r2));
        res = Min(res, Abs(L3 * 3 - n) * d + b + getAns(L3));
        res = Min(res, Abs(r3 * 3 - n) * d + b + getAns(r3));
        res = Min(res, Abs(L5 * 5 - n) * d + c + getAns(L5));
        res = Min(res, Abs(r5 * 5 - n) * d + c + getAns(r5));
        dic[n] = res;
        return res;
    }
}

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

int main(){
	int a, b, c;
	while(1){
		cin >> a >> b >> c;
		if(a == -1 && b == -1 && c == -1)
			break;
		if(a == -1 || b == -1)
			cout << "F\n";
		else if(a+b >= 80)
			cout << "A\n";
		else if(a+b >= 65)
			cout << "B\n";
		else if(a+b >= 50)
			cout << "C\n";
		else if(a+b >= 30 && c < 50)
			cout << "D\n";
		else if(a+b >= 30 && c >= 50)
			cout << "C\n";
		else
			cout << "F\n";
	}
}


Measured memory_bytes: 3052
program main
 implicit none
 integer N,tmp,i,j,k,ans
 integer, allocatable::p(:)
 read(*,*) N
 allocate(p(1:N))
 read(*,*) p
 
 ans = 1
 do i=2,N
  if(p(k) < p(k-1)) then
   ans = -1
   exit
  end if
 end do
 if(ans == -1) then   
  do i=1,N
   tmp = p(i)
   do j=1,N
    if(j == i) continue
    p(i) = p(j)
    p(j) = tmp
    ans = 1
    do k=2,N
     if(p(k) < p(k-1)) then
      ans = -1
      exit
     end if
    end do
    p(j) = p(i)
    p(i) = tmp
    if(ans == 1) exit
   end do
   if(ans == 1) exit
  end do
 end if
 
 if(ans == -1) then
  write(*,*) 'NO'
 else
  write(*,*) 'YES'
 end if
end program main

Measured memory_bytes: 640
n,k = gets.split(' ').map(&:to_i)
first = 0
last = 0
sum = 0
(1..n + 1).each do |i|
  first += i - 1
  last += n - i + 1
  next if k > i
  sum += last - first + 1
  sum = sum % 1000000007
end

puts sum

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

using namespace std;
typedef long long int ll;
#define debug(val) "[ " << #val " : " << (val) << " ]\n"
#define space " "
#define space " "
#define vi vector<int>
#define PI atan(1)*4
#define pb push_back
#define ff first
#define ss second
#define PI atan(1)*4


void solve() {
    int n , k ;
    cin >> n >> k ;
    vi a(n) ;
    for(int i=0;i<n;i++){
        cin >> a[i] ;
    }
    vector<bool> dp(k+1) ;
    for(int i=0;i<=k;i++){
        bool lose = true;
        for(auto val : a ) {
            if(i - val >= 0 ) {
                lose = lose &&   dp[i-val] ;
            }
        }
        dp[i] = !lose ;
    }
//    for(int i=0;i<k;i++){
//        cerr << dp[i] << space ;
//    }
    cout << (dp[k] ? "First" : "Second") << endl;

}
int main() {
#ifdef _DEBUG // place in cmake-build-debug folder
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int q = 1;
    //cin >> q;
    for (int i = 1; i <= q; i++) {
        // cout << "Case #" << i << ": ";
        solve();
    }
}


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

int main()
{
    int n;
    scanf("%d",&n);
    long long  la=1ll,lb=1ll;
    for(int i=1; i<=n; ++i)
    {
        long long  k1=1ll,k2=1ll,a,b;
        scanf("%lld%lld",&a,&b);
        if(a<la)
        {
            k1=la/a;
            if(la%a!=0)
                k1++;
        }
        if(b<lb)
        {
            k2=lb/b;
            if(lb%b!=0)
                k2++;
        }
        k1=max(k1,k2);
        la=a*k1;
        lb=b*k1;
    }
    printf("%lld\n",la+lb);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;

using namespace std;

const long long mod=998244353;

long long p(int x,int n){
    if(n==0)return 1LL;
    long long ans = 1LL;
 //   x %= (unsigned long long)mod;
    rep(i,1,n){
        ans *= (long long)x;
        ans %= (long long)mod;
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    long long ans;
    vector<int> cnt(n);
    rep(i,0,n-1){
        int d;
        cin >> d;
        if(i==0 && d!=0){
            puts("0");
            return 0;
        }
        cnt[d]++;
    }
    if(n==1){
        puts("1");
        return 0;
    }
    ans = (long long)1;
    rep(i,2,n-1){
        if(cnt[0]!=1||(cnt[i]>0 && cnt[i-1]==0)){
            puts("0");
            return 0;
        }
        ans *= p(cnt[i-1],cnt[i]);
        ans = (long long)ans%mod;
    }

    cout << ans%mod << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
 
#define INF 10000000000000LL
 
int N;
vector<ll> A;
vector<int> G[100005];
 
ll dfs(int v, int p){
  if(p!=-1 && G[v].size() == 1) return A[v];
 
  ll sum = 0;
  vector<ll> c;
  rep(i,G[v].size()){
    if(G[v][i] == p) continue;
    ll res = dfs(G[v][i], v);
    if(res<0 || res > A[G[v][i]]) return -INF;
    sum += res;
    c.push_back(res);
  }
  if(c.size() == 1) return c[0];
 
  ll T = 2LL*A[v] - sum;
  if(T<0 || T>A[v]) return -INF;

  sum += T;
  rep(i,c.size()){
    if(c[i] > sum/2) return -INF;
  }
  return T;
}
 
 
bool solve(){
  ll sum = 0;
  ll leaf1 = -1;
  rep(i,N){
    if(G[i].size() == 1){
      sum += A[i];
      leaf1 = i;
    }
  }
  if(sum%2!=0) return false;
  ll n = sum/2;
  rep(i,N){
    if(A[i] > n) return false;
  }
  ll res = dfs(leaf1,-1);
  if(res == A[leaf1]) return true;
  return false;
}
 
int main(){
  cin >> N;
  rep(i,N){
    ll a;
    cin >> a;
    A.push_back(a);
  }
  rep(i,N-1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
 
  if(solve()) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 19060
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
int D,c[26],s[365][26],t[365],v[365],lst[26],m,d[100001],q[100001];

int calc_satisfaction(){
  int stsf=0;
  REP(i,26) lst[i]=0;
  REP(i,D){
    stsf+=s[i][t[i]-1];
    lst[t[i]-1]=i+1;
    REP(j,26) stsf-=c[j]*(i+1-lst[j]);
    //v[i]=stsf;
  }
  return stsf;
}

void chng_t(){
  REP(i,m){
    t[d[i]-1]=q[i];
    cout<<calc_satisfaction()<<endl;
  }
}

int main(){
  cin>>D;
  REP(i,26) cin>>c[i];
  REP(i,D)REP(j,26) cin>>s[i][j];
  REP(i,D) cin>>t[i];
  cin>>m;
  REP(i,m) cin>>d[i]>>q[i];

  chng_t();

  //REP(i,D) cout<<v[i]<<endl;
}

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

int main(){
  int n, x;
  cin >> n >> x;
  int l, d=0, cnt=0;
  for(int i=0; i<n+1; i++){
    if(d<=x)cnt++;
    cin >> l;
    d+=l;
  }
  cout << cnt;
  return 0;
}

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

public class Main {
	static final int mod = (int) 1e9 + 7;
	static final int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };
	static final int[] DX8 = { -1, -1, -1, 0, 0, 1, 1, 1 }, DY8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
	static final int INF = Integer.MAX_VALUE / 3;
	static final long LINF = Long.MAX_VALUE / 3;
	static final String nextLine = "\n";

	static int prime[];
	
	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt();
		List<Integer> ls = new ArrayList<>();
		//素数列挙。練習のためにエラトステネスの篩
		cieve(55555);
		for(int i=0;i<prime.length;i++) {
			if(prime[i] == -1) {
				if(i%5==1)ls.add(i);
			}
		}
		for(int i=0;i<n;i++) {
			System.out.print(ls.get(i) + " ");
		}
		System.out.println();
	}
	
	//x以下の素数を列挙する
	static void cieve(int x) {
		prime = new int[x+1];
		Arrays.fill(prime, -1);
		prime[0] = prime[1] = 0;
		for(int i=2;i<x+1;i++) {
			if(prime[i]!=-1)continue;
			for(int j=2*i;j<x+1;j+=i) {
				prime[j] = i;
			}
		}
	}
	

	//MOD culculations
	static long plus(long x, long y) {
		long res = (x + y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long sub(long x, long y) {
		long res = (x - y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long mul(long x, long y) {
		long res = (x * y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long div(long x, long y) {
		long res = x * pow(y, mod - 2) % mod;
		return res < 0 ? res + mod : res;
	}

	static long pow(long x, long y) {
		if (y < 0)
			return 0;
		if (y == 0)
			return 1;
		if (y % 2 == 1)
			return (x * pow(x, y - 1)) % mod;
		long root = pow(x, y / 2);
		return root * root % mod;
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

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

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

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

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 21972
eval"N,M,A,*B,s=#{`tr -! ,`}[d=x=0]*9e5
B.map{|b|e=b
A>b&&b+=M
x+=t=b-A
[0,M].map{|m|s[m-~A]+=1
s[m+b]-=t
s[m-~b]+=t-1}
A=e}
p x-s.map{d+=$.+=_1}.max"

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		String[] list = str.split("");
		String answer = "yes";
		for(int i=0; i<list.length; i++){
			if(str.length() - str.replace(list[i], "").length() != 1){
				answer = "no";
				break;
			}
		}
		System.out.println(answer);
	}
}




Measured memory_bytes: 22868
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int N, A[100005];
vector <int> G[100005];
bool visited[100005];

int dfs(int x) {
    visited[x] = true;
    if (G[x].size() == 1) return A[x];

    int cost=0, mx=0;
    for (int i = 0; i < G[x].size(); i++) {
        if (visited[G[x][i]]) continue;
        int d = dfs(G[x][i]);
        if (d == -1) return -1;
        cost += d;
        mx = max(d, mx);
    }

    if (A[x] > cost) return -1;
    if (2 * mx < cost && A[x] < cost - (cost/2)) return -1;
    if (2 * mx >= cost && A[x] < mx) return -1;
    return 2 * A[x] - cost;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> N;

    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int max_A=0, max_i=1;
    for (int i = 1; i <= N; i++) {
        if (max_A < A[i] && G[i].size() > 1) {
            max_A = A[i];
            max_i = i;
        }
    }

    if (N == 2) {
        if (A[1] == A[2]) cout << "YES";
        else cout << "NO";
    } else {
        if (dfs(max_i) == 0) cout << "YES";
        else cout << "NO";
    }

    return 0;
}

Measured memory_bytes: 11520
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    readonly Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    List<int>[] G;
    List<int>[] H;
    int[] memo;
    int calc(int u)
    {
        if (memo[u] >= 0)
        {
            return memo[u];
        }

        int ret = 0;
        foreach (var item in H[u])
        {
            chmax(ref ret, calc(item) + 1);
        }
        return memo[u] = ret;
    }
    
    void solve()
    {
        int N = cin.nextint;
        int M = cin.nextint;
        G = new List<int>[N];
        H = new List<int>[N];
        
        for (int i = 0; i < N; i++)
        {
            G[i] = new List<int>();
            H[i] = new List<int>();
        }
        for (int i = 0; i < M; i++)
        {
            int x = cin.nextint - 1;
            int y = cin.nextint - 1;
            G[x].Add(y);
            H[y].Add(x);
        }

        memo = new int[N];
        for (int i = 0; i < N; i++)
        {
            memo[i] = -1;
        }

        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            if (G[i].Count == 0)
            {
                chmax(ref ans, calc(i));
            }
        }
        WriteLine(ans);
    }

}

class Scanner
{
    string[] s; int i;
    readonly char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
    public void join<T>(IEnumerable<T> values) { WriteLine(string.Join(" ", values)); }
}

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

using namespace std;

int main(){
	string s;
	int n;

	cin >> n;
	cin >> s;

	int cnt = 0;

	for(int i = 0 ; i < n ; i++){
		if(i == 0 || s[i - 1] != s[i]){
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}

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


int main (){   
    int N;
  ll M;
  while (cin >> N >> M) {
    vector<ll> A(N);
    for (auto& x : A) cin >> x;
    sort(A.begin(), A.end());
    ll pass = 0, fail = 2 * 1e5 + 10;
    while (fail - pass > 1) {
      ll X = (pass + fail) / 2;
      ll cnt = 0;
      for (int i = 0, j = N - 1; i < N; i++) {
        while (j >= 0 && A[i] + A[j] >= X) --j;
        cnt += N - j - 1;
      }
      if (cnt >= M) {
        pass = X;
      } else {
        fail = X;
      }
    }
    ll res = 0;
    ll sum = 0, rem = M;
    for (int i = 0, j = N - 1; i < N; i++) {
      while (j >= 0 && A[i] + A[j] > pass) {
        sum += A[j];
        --j;
      }
      ll c = N - j - 1;
      rem -= c;
      res += sum + c * A[i];
    }
    res += pass * rem;
    cout << res << endl;
  }
  return 0;
}



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

using namespace std;

int main(){

int x;
int y;
int n;
cin >> n;
int v[n];
int c[n];

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

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


for(int i = 0; i < n; i++){
	if(v[i] - c[i] > 0){
		x = x + (v[i] - c[i]);
	}
}

cout << x << endl;

  return 0;
}

Measured memory_bytes: 256
from collections import*
h,*t=open(0)
h,w=map(int,h.split())
f,o=1,0
for i in Counter(''.join(t[:-1]for t in t)).values():
    f+=i//4
    o+=i&1
print('YNeos'[o>h%2*w%2or h//2*(w//2)>=f::2])

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

using PII = pair<int, int>;
int main() {
  int n, m, p;
  cin >> n >> m >> p;
  vector<vector<PII>> g(n + 1);
  vector<vector<int>> rg(n + 1);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    w = -(w - p);
    g[u].emplace_back(v, w);
    rg[v].push_back(u);
  }
  vector<bool> reach(n + 1);
  {
    queue<int> q;
    q.push(n);
    reach[n] = true;
    while (q.size()) {
      int x = q.front();
      q.pop();
      for (int y : rg[x]) {
        if (!reach[y]) {
          reach[y] = true;
          q.push(y);
        }
      }
    }
  }
  constexpr int inf = 1e9;
  vector<int> d(n + 1, inf);
  d[1] = 0;
  queue<int> q;
  vector<bool> inq(n + 1);
  q.push(1);
  vector<int> in(n + 1);
  while (q.size()) {
    int x = q.front();
    q.pop();
    inq[x] = false;
    in[x]++;
    if (!reach[x]) continue;
    if (in[x] == n + 10) {
      cout << -1 << endl;
      return 0;
    }
    for (auto &it : g[x]) {
      int y, w;
      tie(y, w) = it;
      if (d[x] + w < d[y]) {
        d[y] = d[x] + w;
        if (!inq[y]) {
          inq[y] = true;
          q.push(y);
        }
      }
    }
  }
  if (d[n] == inf) {
    cout << -1 << endl;
  } else {
    cout << max(0, -d[n]) << endl;
  }
  return 0;
}



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

int main(){
  string s;
  cin>>s;
  int d=0,p=0;
  rep(i,s.size()){
    if(s[i]=='g'){
      if(d>0){
	p++;
	d--;
      }
      else{
	d++;
      }
    }
    else{
      if(d>0){
	d--;
      }
      else{
	p--;
	d++;
      }
    }
  }
  cout<<p<<endl;
  return 0;
}

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

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=1e6+7;
const int mod=1e9+7;

int r,c,n,x,y,ans[200][200];

int main(void)
{
    scanf("%d%d%d",&r,&c,&n);
    x=1,y=1;
    for(int i=1,cnt;i<=n;i++)
    {
        scanf("%d",&cnt);
        while(cnt--)
        {
            ans[x][y]=i;
            if(y==c&&x%2==1)
                y=c,x++;
            else if(y==1&&x%2==0)
                y=1,x++;
            else if(x&1)
                y++;
            else
                y--;
        }
    }
    for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
        printf("%d%c",ans[i][j],j==c?'\n':' ');
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

template<typename T>
struct LazySegmentTree{
private:
    int n;
    vector<T> node,lazy;
    vector<bool> flg;
public:
    T SUP=0; /* 初期値　*/
    T merge(T x,T y){
        return x+y;
    }
    LazySegmentTree(vector<T> v){
        int sz=(int)v.size();
        n=1; while(n<sz) n*=2;
        node.resize(2*n-1);
        lazy.resize(2*n-1,0);
        flg.resize(2*n-1,false);
        for(int i=0;i<sz;i++) node[i+n-1]=v[i];
        for(int i=n-2;i>=0;i--) node[i]=merge(node[2*i+1],node[2*i+2]);
    }
    void eval(int idx,int l,int r){
        if(flg[idx]){
            flg[idx]=false;
            node[idx]=lazy[idx];
            if(r-l>1){
                /* node[idx]からの伝播  */
                lazy[2*idx+1]=lazy[idx]/2;
                lazy[2*idx+2]=lazy[idx]/2;
                flg[2*idx+1]=flg[2*idx+2]=true;
            }
            lazy[idx]=0;
        }
    }
    void update(int a,int b,T x,int idx=0,int l=0,int r=-1){
        if(r<0) r=n;
        eval(idx,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            lazy[idx]=x*(r-l);
            flg[idx]=true;
            eval(idx,l,r);
        }else{
            update(a,b,x,2*idx+1,l,(l+r)/2);
            update(a,b,x,2*idx+2,(l+r)/2,r);
            node[idx]=merge(node[2*idx+1],node[2*idx+2]);
        }
    }
    T query(int a,int b,int idx=0,int l=0,int r=-1){
        if(r<0) r=n;
        if(b<=l || r<=a) return 0;
        eval(idx,l,r);
        if(a<=l && r<=b) return node[idx];
        T vl = query(a,b,2*idx+1,l,(l+r)/2);
        T vr = query(a,b,2*idx+2,(l+r)/2,r);
        return merge(vl,vr);
    };
};



signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,q; cin >> n >> q;
    vector<ll> v(n,0);
    LazySegmentTree<ll> lsg(v);
    rep(i,q){
        int x; cin >> x;
        if(x==0){
            int s,t,y; cin >> s >> t >> y;
            t++;
            lsg.update(s,t,y);
        }else{
            int s,t; cin >> s >> t;
            t++;
            cout << lsg.query(s,t) << "\n";
        }
    }

}



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

int main() {
  vector<int> num(5e5,0);
  string s;
  cin >> s;
  vector<int> id={0,1};
  s='>'+s+'<';
  for(int i=0;i<s.size()-1;i++) {
    if(s.at(i)=='>'&&s.at(i+1)=='<') {
      num.at(i)=0;
      queue<int> q;
      q.push(i);
      while(q.size()) {
        int temp=q.front();
        q.pop();
        for(int j=0;j<2;j++) {
          int nn=temp+id.at(j);
          if(nn-1>-1&&nn<s.size()-1) {
            if(nn==temp&&s.at(nn)=='>') {
              q.push(nn-1);
              num.at(nn-1)=max(num.at(nn-1),num.at(temp)+1);
            }
            else if(nn>temp&&s.at(nn)=='<') {
              q.push(nn);
              num.at(nn)=max(num.at(nn),num.at(temp)+1);
            }
          }
        }
      }
    }
  }
  long long ans=0;
  for(int i=0;i<s.size()-1;i++) {
    ans+=num.at(i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3332
S = input()

# dp[i][n] := i文字目までのNONE,A,AB,ABCを決めた数
dp = [[0]*4 for i in range(len(S)+1)]
NO, A, AB, ABC = 0, 1, 2, 3
MOD = 10**9+7
dp[0][NO] = 1
for i in range(len(S)):
    # カウントを進めない時
    for j in range(4):
        if S[i] == "?":
            dp[i+1][j] += dp[i][j]*3
        else:
            dp[i+1][j] += dp[i][j]
    # それ以外
    if S[i] == "A" or S[i] == "?":
        dp[i+1][A] += dp[i][NO]
    if S[i] == "B" or S[i] == "?":
        dp[i+1][AB] += dp[i][A]
    if S[i] == "C" or S[i] == "?":
        dp[i+1][ABC] += dp[i][AB]
    for j in range(4):
        dp[i+1][j] %= MOD
    
print(dp[len(S)][ABC])


    


Measured memory_bytes: 27624
#include <stdio.h>
#include <ctype.h>
#include <string.h>


int main()
{
	char szLine[200];
	fgets(szLine, sizeof(szLine), stdin);
	char* p = strchr(szLine, ' ');
	p++;
	char cUp = toupper(*p);
	printf("A%cC", cUp);

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define lcm( a, b ) ((a)/__gcd(a,b)*(b))
#define MP make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef pair< LL, LL > L_P;

const int INF = INT_MAX;
const int MIN = INT_MIN;
const LL LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;
const int SIZE = 1005;

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

int bfs();
vector< P > black;

int mp[SIZE][SIZE];

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

    int h, w;
    cin >> h >> w;
    for( int i = 0; i <= h + 1; ++i ) {
        for( int j = 0; j <= w + 1; ++j ) {
            mp[i][j] = 1;

        }
    }

    for( int i = 1; i <= h; ++i ) {
        for( int j = 1; j <= w; ++j ) {
            char c;
            cin >> c;
            if( c == '.' ) {
                mp[i][j] = 0;

            } else {
                black.pb( MP( i, j ) );

            }
        }
    }

    cout << bfs() << endl;
    return 0;
}

int bfs() {
    queue< i_P > q;
    for( int i = 0; i < black.size(); ++i ) {
        q.push( MP( 0, MP( black[i].F, black[i].S ) ) );

    }

    int res = 0;
    while( !q.empty() ) {
        i_P p = q.front(); q.pop();

        for( int i = 0; i < 4; ++i ) {
            if( mp[p.S.F + dx[i]][p.S.S + dy[i]] == 0 ) {
                mp[p.S.F + dx[i]][p.S.S + dy[i]] = 1;
                q.push( MP( p.F + 1, MP( p.S.F + dx[i], p.S.S + dy[i] ) ) );
                res = max( p.F + 1, res );

            }
        }

    }

    return res;
}



Measured memory_bytes: 24168
using System;
namespace ITP1_2_A {
	class Program {
		static void Main(string[] args) {
			string[] s = Console.ReadLine().Split();
			int a = int.Parse(s[0]), b = int.Parse(s[1]);
			if (a > b) Console.WriteLine("a > b");
			else if (a < b) Console.WriteLine("a < b");
			else Console.WriteLine("a == b");
		}
	}
}

Measured memory_bytes: 8720
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <limits>
#include <iomanip>
#include <queue>
#include <cmath>
#include <math.h>
#include <string>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;
using pll = pair<long long, long long>;
typedef long long ll;
#define min(a, b) ((a) < (b) ? (a) : (b))
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

vector<int> IntegerToVector(int bit, int N) {
	vector<int> S;
	for (int i = 0; i < N; i++) {
		if (bit & (1 << N)) {
			S.push_back(i);
		}
	}
	return S;
}

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

	char A[12];
	int N;
	cin >> A;
	N = strlen(A);
	long long S = 0;
	for (int i = 0; i < (1 << (N - 1)); i++) {
		long long tmp = A[0] - '0';
		for (int j = 0; j < N - 1; j++) {
			if (i & (1 << j)) {
				S += tmp;
				tmp = 0;
			}
			tmp = tmp * 10 + A[j + 1] - '0';
		}
		S += tmp;
	}
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 384
c = [list(map(int, input().split())) for _ in range(3)]

ans = "No"

for a_1 in range(101):
  b_1 = c[0][0] - a_1
  b_2 = c[0][1] - a_1
  b_3 = c[0][2] - a_1
  a_2 = c[1][0] - b_1
  a_3 = c[2][0] - b_1
  if a_2+b_2==c[1][1] and a_2+b_3==c[1][2] and a_3+b_2==c[2][1] and a_3+b_3==c[2][2]:
    ans = "Yes"
    break

print(ans)

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

const int INF=1e9;

int dp[1<<13];

int main(){
    int N,M; cin >> N >> M;
    for(int i=0;i<(1<<N);i++){
        dp[i]=INF;
    }
    dp[0]=0;
    for(int i=0;i<M;i++){
        int a,b; cin >> a >> b;
        int k=0;
        for(int j=0;j<b;j++){
            int c; cin >> c; c--;
            k+=(1<<c);
        }
        for(int mask=0;mask<(1<<N);mask++){
            dp[mask|k]=min(dp[mask|k],dp[mask]+a);
        }
    }
    if(dp[(1<<N)-1]==INF) cout << -1 << endl;
    else cout << dp[(1<<N)-1] << endl;
}

Measured memory_bytes: 256