Submission #1228462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228462		minhpk	Genetics (BOI18_genetics)	C++20	100 / 100	323 ms	52868 KiB

genetics

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
string z[1000005];
int t[4101][5];
vector <int> snt;
bool check[1000005];
int val[1000005];

void sangnguyento(){
    for (int i=2;i<=1e6;i++){
         check[i]=true;
    }
    for (int i=2;i<=1e6;i++){
        if (check[i]){
             for (int j=i*i;j<=1e6;j+=i){
                  check[j]=false;
             }
        }
    }
    for (int i=2;i<=1e6;i++){
         if (check[i]){
             snt.push_back(i);
         }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sangnguyento();
    cin >> a >> b >> c;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         val[i]=snt[i];
         for (int j=1;j<=b;j++){
              if (z[i][j-1]=='A'){
                  t[j][1]+=val[i];
              }else if (z[i][j-1]=='T'){
                  t[j][2]+=val[i];
              }else if (z[i][j-1]=='G'){
                  t[j][3]+=val[i];
              }else{
                  t[j][4]+=val[i];
              }
         }
    }
    int sumval=0;
    for (int i=1;i<=a;i++){
        sumval+=val[i]*c;

    }
    for (int i=1;i<=a;i++){
         int sum=0;
         int req=sumval-val[i]*c;
         for (int j=1;j<=b;j++){
              if (z[i][j-1]=='A'){
                  sum+=t[j][2]+t[j][3]+t[j][4];
              }else if (z[i][j-1]=='T'){
                  sum+=t[j][1]+t[j][3]+t[j][4];
              }else if (z[i][j-1]=='G'){
                  sum+=t[j][2]+t[j][1]+t[j][4];
              }else{
                  sum+=t[j][2]+t[j][3]+t[j][1];
              }
         }
        if (sum==req){
            cout << i << "\n";
            return 0;
        }
    }

    return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26